4354: 「JOI 2016 Final」橙子装箱
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**本题译自 [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T1「[オレンジの出荷](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)」**
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$ 个橙子所需的最小成本。
样例输入 复制
6 3 6
1
2
3
1
2
1样例输出 复制
21提示
输入样例2
16 4 12 3 10 13 10 19 9 12 16 11 2 19 9 13 2 13 19
输出样例2
164
输入样例3
16 6 14 19 7 2 15 17 7 14 12 3 14 5 10 17 20 19 12
输出样例3
177
输入样例4
10 1 1000000000 1 1 1 1 1 1 1 1 1 1
输出样例4
10000000000
数据范围：对于所有数据，$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$。 |Subtask #|$N$|$M$|分值| |-|-|-|-| |1|$N\leqslant 20$|$M\leqslant 1000$|20| |2|$N\leqslant 2000$|$M\leqslant 100$|50| |3|$N\leqslant 2\times 10^4$|$M \leqslant 1000$|30|