题目描述

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

一个箱子内最多可以装 $m$ 个橙子。在一个箱子内装一些橙子的成本为

其中 $k$ 是箱子本身的成本（所有箱子的成本一样），$s$ 是该箱子中橙子的数目，$a$ 是该箱子中最大橙子的大小，$b$ 是该箱子中最小橙子的大小。

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

输入格式

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

接下来的 $n$ 行中，第 $i$ 行 $(1\le i\le 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

说明

数据范围

• $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）：无特殊限制。