橙子装箱
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

本题译自 JOI 2016 Final T1「オレンジの出荷」
JOI社决定将收获的N个橙子分装进一些箱子内。在JOI社的工厂中，橙子排列在输送带上，依次编号为。橙子的大小为A_i。由于分拣不方便，同一个箱子内，橙子的编号必须连续。
一个箱子内最多可以装M个橙子。在一个箱子内装一些橙子的成本为K+s×(a−b)。K是箱子本身的成本，所有箱子的成本一样。s是该箱子中橙子的数目。a是该箱子中最大橙子的大小，b是该箱子中最小橙子的大小。
求包装这N个橙子所需的最小成本。

输入描述:

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

输出描述:

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

输入

复制 
6 3 6
1
2
3
1
2
1

输出

复制 
21

说明

用两个箱子装。第一个箱子装橙子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

输出

复制 
164

说明

用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

输出

复制 
177
示例4

输入

复制 
10 1 1000000000
1
1
1
1
1
1
1
1
1
1

输出

复制 
10000000000

说明

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

备注:

对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自https://loj.ac/problem/2342