AT_joi2016ho_a オレンジの出荷 (Oranges)

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「オレンジの出荷」