题目描述

CXR决定将收获的$n$个橙子分装进一些箱子内。在NXY的工厂中，橙子排列在输送带上，依次编号为$1...n$。橙子$i(1\leq i\leq n$)的大小为$A_i$。由于分拣不方便，同一个箱子内，橙子的编号必须连续。

一个箱子内最多可以装$m$个橙子。在一个箱子内装一些橙子的成本为$k+s\times (a-b)$。$k$是箱子本身的成本，所有箱子的成本一样。$s$是该箱子中橙子的数目。 $a$是该箱子中最大橙子的大小，$b$是该箱子中最小橙子的大小。

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

输入格式

第一行有三个整数$n,m,k$，用空格分隔。

在接下来的$n$行中，第$i$行$(1\leq i\leq n)$有一个整数$A_i$。

输入的所有数的含义见题目描述。

输出格式

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

输入样例 1

6 3 6
1
2
3
1
2
1

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

样例解释 4

答案可能会爆$int$。

数据范围

• 1≤N≤20 000
• 1≤M≤1 000
• 0≤K≤1 000 000 000
• 1≤A_i≤1 000 000 000 (1≤i≤N)
• M≤N

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