Pile of Laundry

The washing machine has been broken for a week, so laundry has accumulated. You must divide the clothes into piles. Each item has a drying time $T_i$, and each pile may contain at most $C$ items (the machine capacities). The piles are washed sequentially, and each wash takes $W$ time.

After a pile is washed, it is placed immediately into the drying machine. A pile finishes drying when its slowest item finishes. The next pile cannot begin drying until the previous one has fully dried, so the drying machine must be empty before the next pile is placed.
Loading and unloading the machine takes 0 time.

Task

Find a partition of the clothes into piles that minimizes the total time to wash and dry all items.

Input data

The input file consists of:

• a line containing integers $N$, $C$, $W$ - the number of clothes, the capacity of the washing machine, and the washing time for a pile.
• a line containing $N$ integers $T_{0}, \, \ldots, \, T_{N-1}$ - the drying times of the clothes.

Output data

Print one integer $\mathtt{ans}$, the total time required to finish all laundry.

Constraints and clarifications

• $1 \le N \le 100 \ 000$.
• $1 \le C \le 1 \ 000$.
• $1 \le W \le 1 \ 000$.
• $1 \le T_i \le 10 \ 000$ for each $i=0\ldots N-1$.

Example 1

stdin

5 2 1
1 10 2 9 3

stdout

15

Explanation

In the first sample case, the batches (by drying time) are $[10,9]$, $[3,2]$, and $[1]$. Batch 1 finishes washing at time 1 and dries from 1-11. Batch 2 finishes washing at time 11 and dries from 11-14. Batch 3 finishes washing at time 14 and dries from 14-15. This schedule is shown below, and it can be proven that it is optimal.

Example 2

stdin

5 2 100
3 9 2 10 1

stdout

301

Explanation

In the second sample case, the batches (by drying time) can be $[10,2]$, $[9,3]$, and $[1]$. Batch 1 finishes washing at time 100 and dries from 100-110. Batch 2 finishes washing at time 200 and dries from 200-209. Batch 3 finishes washing at time 300 and dries from 300-301. It can be proven that it is optimal.