题目描述

本题译自 JOI 2016 Final T1「オレンジの出荷」

JOI 社决定将收获的 $N$ 个橙子分装进一些箱子内。在 JOI 社的工厂中，橙子排列在输送带上，依次编号为 $1\ldots N$。橙子 $i\,(1\leqslant i \leqslant N)$ 的大小为 $A_i$。由于分拣不方便，同一个箱子内，橙子的编号必须连续。
一个箱子内最多可以装 $M$ 个橙子。在一个箱子内装一些橙子的成本为 $K + s × (a − b)$。$K$ 是箱子本身的成本，所有箱子的成本一样。$s$ 是该箱子中橙子的数目。$a$ 是该箱子中最大橙子的大小，$b$ 是该箱子中最小橙子的大小。

求包装这 $N$ 个橙子所需的最小成本。

输入格式

第一行有三个整数 $N, M, K$，用空格分隔。
在接下来的 $N$ 行中，第 $i$ 行 $(1\leqslant i\leqslant N)$ 有一个整数 $A_i$。
输入的所有数的含义见题目描述。

输出格式

输出一个整数，表示包装这 $N$ 个橙子所需的最小成本。

样例 1

input

6 3 6
1
2
3
1
2
1

output

21

用两个箱子装。第一个箱子装橙子 $1,2,3$，第二个箱子装 $4,5,6$，总成本为 $[6+3×(3−1)]+[6+3×(2−1)] = 21$。

样例 2

input

16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

output

164

用 $11$ 个箱子装。这些箱子依次分别装了 $1, 3, 1, 1, 3, 1, 1, 2, 1, 1, 1$ 个橙子，箱子 $1$ 装了橙子 $1$，箱子 $2$ 装了橙子 $2, 3, 4$，箱子 $3$ 装了橙子 $5$，以此类推。

样例 3

input

16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12

output

177

样例 4

input

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

output

10000000000

答案可能会爆 $\texttt{int}$ 。

数据范围与提示

对于所有数据，$1\leqslant N\leqslant 2\times 10^4, 1\leqslant M\leqslant 1000, 0\leqslant K\leqslant 10^9, 1\leqslant A_i\leqslant 10^9(1\leqslant i\leqslant N), M\leqslant N$。