F. Coffee is Life
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On his voyage to hunt the elusive white whale, Captain Ahab is swamped with tasks to do during day-to-day life on his ship. The good news is that he has the life-sustaining power of coffee on his side. The bad news is that there is a limited amount of coffee in his ship's hold. There are $$$n$$$ days, each with some amount of work $$$w_i$$$ to do. Each unit of work costs 1 energy, and every day starts with 0 energy.

There are $$$m$$$ cups of coffee that can be drunk on any day. The first coffee drunk on any day gives $$$k$$$ energy, the second gives $$$k-1$$$ energy, and so on, until the $$$k^{th}$$$ coffee gives $$$1$$$ energy; any coffee drunk afterward gives no energy.

Ahab needs your help to ration his coffee to complete as much work as possible.

Input

The first line of input contains $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 10^5, 1 \le m, k \le 10^9$$$), the number of days, cups of coffee, and initial energy from coffee, respectively.

The second line contains $$$n$$$ integers, $$$w_1, w_2, ..., w_n$$$ ($$$1 \le w_i \le 10^{18}$$$), the amount of work to be done each day.

Output

The output should be one line containing the maximum possible amount of work that can be done.

Example
Input
4 4 3
10 2 4 1
Output
10
Note

It is optimal for Ahab to drink two coffees on the first day, one on the second day, and one on the third day for $$$5+2+3 = 10$$$ units of work total.