题目描述

翁老师决定将收获的 $n$ 个橙子分装进一些箱子内。在 贝尔 的工厂中，橙子排列在输送带上，依次编号为 $1\dots n$。第 $i$ 个橙子的大小为 $a_i$。由于分拣不方便，同一个箱子内，橙子的编号必须连续。

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

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

输入格式

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

在接下来的 $n$ 行中，第 $i$ 行输入一个整数 $a_i$。

输出格式

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

6 3 6
1
2
3
1
2
1

21

样例 1 解释

最优方案之一如下：

• 将 $[1,2,3]$ 放入第一个箱子，代价为 $6+3\times (3-1)=12$
• 将 $[4,5,6]$ 放入第一个箱子，代价为 $6+3\times (2-1)=9$

总代价为 $21$。

16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

164

16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12

177

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

10000000000

数据范围

对于 $100\%$ 的数据满足：$1\leq n\leq 2\times 10^4$，$1\leq m\leq 10^3$，$0\leq k\leq 10^9$，$1\leq a_i\leq 10^9$，$m\leq n$。

本题采取捆绑测试

• 子任务 $1$（$20$ 分）：$n\le 20$。
• 子任务 $2$（$50$ 分）：$n \le 2000,m \le 100$。
• 子任务 $3$（$30$ 分）：无特殊限制。