你知道 Juicy Orange Industry 公司吗？这家公司的业务是种植并销售美味的橙子。以下简称 JOI 公司。

JOI 公司决定将收获的 $N$ 个橙子装箱后出货。橙子在工厂的传送带上排成一列，从传送带前端开始依次编号为 $1$ 到 $N$。橙子大小各异，橙子 $i$ ($1 \le i \le N$) 的大小为 $A_i$。

这些橙子需要按顺序装入若干个箱子中。一个箱子只能装入编号连续的橙子。

一个箱子最多可以装入 $M$ 个橙子。装入某个箱子的成本，设该箱中橙子的最大大小为 $a$，最小大小为 $b$，橙子个数为 $s$，则可以通过 $K + s \times (a - b)$ 计算得出。其中，$K$ 是每个箱子的固定成本，对于所有箱子该值相同。

请准备合适数量的箱子，将所有橙子妥善装箱，使得装箱的总成本尽可能小。

题目描述

给定传送带上橙子的信息、一个箱子能装入的橙子最大个数以及箱子的固定成本，编写一个程序，求出装箱总成本的最小值。

输入格式

从标准输入读取以下内容：

• 第 $1$ 行包含 $3$ 个整数 $N, M, K$，以空格分隔。这表示有 $N$ 个橙子，一个箱子最多能装入 $M$ 个橙子，箱子的固定成本为 $K$。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含一个整数 $A_i$，表示橙子 $i$ 的大小为 $A_i$。

输出格式

将装箱总成本的最小值输出到标准输出，占一行。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 20\,000$
• $1 \le M \le 1\,000$
• $0 \le K \le 1\,000\,000\,000$
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $M \le N$

子任务

子任务 1 [20 分] * 满足 $N \le 20$。

子任务 2 [50 分] 满足以下条件： $N \le 2\,000$ * $M \le 100$

子任务 3 [30 分] * 无附加限制。

样例

样例输入 1

6 3 6
1
2
3
1
2
1

样例输出 1

21

说明 1

若第 $1$ 个箱子装入从橙子 $1$ 到橙子 $3$ 的 $3$ 个橙子，第 $2$ 个箱子装入从橙子 $4$ 到橙子 $6$ 的 $3$ 个橙子，则装箱总成本为 $(6+3 \times (3-1)) + (6+3 \times (2-1)) = 21$。 无论如何装箱，总成本都不会低于 $21$，因此输出 $21$。

样例输入 2

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

样例输出 2

164

说明 2

准备 $11$ 个箱子，按顺序分别装入 $1, 3, 1, 1, 3, 1, 1, 2, 1, 1, 1$ 个橙子，可使总成本最小。

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

请注意，答案不一定在 $32$ 位有符号整数的范围内。