#2342. 「JOI 2016 Final」橙子装箱

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

本题译自 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

6 3 6
1
2
3
1
2
1

输出样例 1

21

样例解释 1

用两个箱子装。第一个箱子装橙子 1,2,3 ,第二个箱子装 4,5,6 ,总成本为 [6+3×(3−1)]+[6+3×(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

样例解释 2

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

样例输入 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

样例解释 4

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

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