AT_arc182_e.[ARC182E] Sum of Min of Mod of Linear

给定正整数 $N, M, K$，非负整数 $C$，以及一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。

请计算 $\displaystyle\sum_{k=0}^{K-1} \min_{1 \leq i \leq N} \{ (Ck + A_i) \bmod M \}$ 的值。

输入以以下格式从标准输入读入。

$N$ $M$ $C$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出答案。

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^9$
• $0 \leq C < M$
• $1 \leq K \leq 10^9$
• $0 \leq A_i < M$
• 所有输入均为整数

样例解释 1

当 $k=0$ 时，$\{(3k+1)\bmod 5\}=1$，$\{(3k+3)\bmod 5\}=3$，所以 $\displaystyle\min_{1\leq i\leq N}\{(Ck+A_i)\bmod M\}=1$。
当 $k=1$ 时，$\{(3k+1)\bmod 5\}=4$，$\{(3k+3)\bmod 5\}=1$，所以 $\displaystyle\min_{1\leq i\leq N}\{(Ck+A_i)\bmod M\}=1$。
当 $k=2$ 时，$\{(3k+1)\bmod 5\}=2$，$\{(3k+3)\bmod 5\}=4$，所以 $\displaystyle\min_{1\leq i\leq N}\{(Ck+A_i)\bmod M\}=2$。
因此，答案为 $1+1+2=4$，请输出 $4$。

由 ChatGPT 4.1 翻译