题目描述

CXR 决定将收获的 $n$ 个橙子分装进一些箱子内。在 NXY 的工厂中，橙子排列在输送带上，依次编号为 $1\dots 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

输入 #1

6 3 6
1
2
3
1
2
1

输出 #1

21

输入输出样例 #2

输入 #2

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

输出 #2

164

输入输出样例 #3

输入 #3

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

输出 #3

177

输入输出样例 #4

输入 #4

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

输出 #4

10000000000

说明/提示

【数据范围与约定】

• $1\le N\le 2\times 10^4$。
• $1\le M\le 10^3$。
• $0\le K\le 10^9$。
• $1\le A_i\le 10^9 (1\le i\le N)$。
• $M\le N$。

1. Subtask $1$（$20$ pts）：$N\le 20$。
2. Subtask $2$（$50$ pts）：$N \le 2000,M \le 100$。
3. Subtask $3$（$30$ pts）：无特殊限制。