Orange Shipping

Juicy Orange Industry (JOI) is a company that packs oranges into boxes and ships them.

JOI ships the $N$ oranges it has collected by putting them into boxes. The oranges are first laid out in a row on a conveyor belt in the factory. The oranges on the belt are numbered $1$ through $N$ from the front, and the size of orange $i$ is $A_i$.

The next step is to put the oranges into boxes, in order from the front. The numbers of the oranges placed in one box must be consecutive.

One box holds at most $M$ oranges. The cost of filling a box is $K + s \times (a - b)$, where $a$ is the largest orange size in that box, $b$ is the smallest size, and $s$ is the number of oranges in it. $K$ is the fee for packing a box and is the same for every box.

Given the oranges on the conveyor belt, the maximum number of oranges that one box holds, and the packing fee $K$, write a program that finds the minimum total cost of packing all of the oranges.

The first line contains the number of oranges $N$ ($1 \le N \le 20\,000$), the maximum number of oranges in one box $M$ ($1 \le M \le 1\,000$, $M \le N$), and the packing fee $K$ ($0 \le K \le 1\,000\,000\,000$), separated by spaces.

Each of the next $N$ lines contains one orange size $A_i$ ($1 \le A_i \le 1\,000\,000\,000$), given in order.

Print the minimum total cost of packing all of the oranges on the first line.