Problem Description

Do you know the Juicy Orange Industry company? This company's business is to cultivate and ship delicious oranges. Here, we will refer to it as JOI Inc.

JOI Inc has decided to pack and ship $ N $ harvested oranges into boxes. The oranges are arranged on a conveyor belt in the factory, and are numbered from $ 1 $ to $ N $ in the order from the front of the conveyor belt. The oranges vary in size, and the size of orange $ i $ ($1 \leq i \leq N$) is $ A_i $.

These oranges will be packed into several boxes in the order from the front. One box can only contain oranges with consecutive numbers.

Each box can contain up to $ M $ oranges. The cost to pack several oranges into one box is determined by the maximum size $ a $ of the oranges in the box, the minimum size $ b $ of the oranges in the box, and the number of oranges $ s $ in the box, calculated as $K + s \times (a - b)$. Here, $ K $ is the cost associated with the box, a common value for all boxes.

You want to pack all the oranges into an appropriate number of boxes in a way that minimizes the total packing cost.

Input Format

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 associated with the box is $ K $.
• The following $ N $ lines contain an integer $ A_i $ each. This represents the size of orange $ i $.

Output Format

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

Sample Input and Output

Sample Input #1

6 3 6
1
2
3
1
2
1

Sample Output #1

21

Sample Input #2

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

Sample Output #2

164

Sample Input #3

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

Sample Output #3

177

Sample Input #4

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

Sample Output #4

10000000000

Notes/Hints

Task

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

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [20 points]

• $N \leq 20$.

Subtask 2 [50 points]

Satisfies the following conditions:

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

Subtask 3 [30 points]

No additional constraints.

Sample Explanation 1

Packing oranges $ 1 $ to $ 3 $ into the first box and oranges $ 4 $ to $ 6 $ into the second box results in a total packing cost of $(6 + 3 \times (3 - 1)) + (6 + 3 \times (2 - 1)) = 21$. No other packing method results in a total cost lower than $ 21 $, so output $ 21 $.

Sample Explanation 2

Prepare 11 boxes and pack the oranges into them in the order of $ 1 $ orange, $ 3 $ oranges, $ 1 $ orange, $ 1 $ orange, $ 3 $ oranges, $ 1 $ orange, $ 1 $ orange, $ 2 $ oranges, $ 1 $ orange, $ 1 $ orange, and $ 1 $ orange, respectively, to minimize the total packing cost.

Sample Explanation 3

Sample Explanation 4

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

见题面 Input 部分

见题面 Output 部分