Do you know the Juicy Orange Industry company? This company's business is to grow and ship delicious oranges. Here, we will call it the JOI company for short.

The JOI company has decided to pack $N$ harvested oranges into boxes for shipping. The oranges are lined up on a conveyor belt in the factory, and are numbered from $1$ to $N$ in order from the front of the conveyor belt. The oranges vary in size, and the size of orange $i$ ($1 \le i \le N$) is $A_i$.

These oranges are packed into several boxes in order from the front. A single box can only contain oranges with consecutive numbers.

A single box can hold at most $M$ oranges. The cost to pack some oranges into a box can be calculated as $K + s \times (a - b)$, where $a$ is the size of the largest orange in the box, $b$ is the size of the smallest orange in the box, and $s$ is the number of oranges in the box. Here, $K$ is the cost per box, which is a constant value for all boxes.

We want to minimize the total cost of packing by preparing an appropriate number of boxes and packing all the oranges appropriately.

Task

Given information about the oranges on the conveyor belt, the maximum number of oranges that can be packed into a single box, and the cost per box, write a program to find the minimum total cost of packing.

Input

Read the following input from standard input:

• The first line contains three integers $N, M, K$ separated by spaces. This indicates that there are $N$ oranges, the maximum number of oranges that can be packed into one box is $M$, and the cost per box is $K$.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains an integer $A_i$. This indicates that the size of orange $i$ is $A_i$.

Output

Output the minimum total cost of packing in a single line to standard output.

Constraints

All input data satisfies the following conditions:

• $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$.

Subtasks

Subtask 1 [20 points]

• $N \le 20$ is satisfied.

Subtask 2 [50 points]

The following conditions are satisfied:

• $N \le 2\,000$.
• $M \le 100$.

Subtask 3 [30 points]

There are no additional constraints.

Examples

Input 1

6 3 6
1
2
3
1
2
1

Output 1

21

Note 1

If you pack 3 oranges from orange 1 to orange 3 in the first box, and 3 oranges from orange 4 to orange 6 in the second box, the total cost of packing is $(6 + 3 \times (3 - 1)) + (6 + 3 \times (2 - 1)) = 21$. Since the total cost of packing cannot be less than 21 no matter how you pack them, output 21.

Input 2

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

Output 2

164

Note 2

By preparing 11 boxes and packing 1, 3, 1, 1, 3, 1, 1, 2, 1, 1, 1 oranges into each box in order from the front, the total cost of packing is minimized.

Input 3

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

Output 3

177

Input 4

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

Output 4

10000000000

Note 4

Note that the answer may not fit within the range of a 32-bit signed integer.