2342 「JOI 2016 Final」橙子装箱

本题译自 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,2,3$，第二个箱子装 $4,5,6$，总成本为 $[6+3×(3−1)]+[6+3×(2−1)] = 21$。

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

答案可能会爆 $\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$。