题目描述

给定正整数 $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

输入 #1

2 5 3 3
1 3

输出 #1

4

输入输出样例 #2

输入 #2

5 4 3 182
0 3 2 1 2

输出 #2

0

输入输出样例 #3

输入 #3

5 718 651 193855
3 532 44 109 58

输出 #3

29484897

说明/提示

限制条件

• $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$。