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.
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.
The output should be one line containing the maximum possible amount of work that can be done.
4 4 310 2 4 1
10
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.
