Problem Statement

Takahashi is planning an $N$-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for $1\leq i\leq N$, the regular fare for the $i$-th day of the trip is $F_i$ yen.
On the other hand, a batch of $D$ one-day passes is sold for $P$ yen. You can buy as many passes as you want, but only in units of $D$.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the $N$-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• $1\leq N\leq 2\times 10^5$
• $1\leq D\leq 2\times 10^5$
• $1\leq P\leq 10^9$
• $1\leq F_i\leq 10^9$
• All input values are integers.

Sample Input 1Copy

5 2 10
7 1 6 3 6

Sample Output 1Copy

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be $(10\times 1)+(0+1+0+3+6)=20$, which is the minimum cost needed.
Thus, print $20$.

Sample Input 2Copy

3 1 10
1 2 3

Sample Output 2Copy

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3Copy

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3Copy

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a $32$-bit integer type.