— Billy, you are wasting your life on computer games! — That's OK, Mom, I have three lives left!
In the Great Battle to save everything good in this world, $H$ heroes are fighting a horde of $M$ monsters. The combatants are standing in a circle, in a given order. The $i$-th hero is followed on the circle by $m_i$ monsters (such that $m_1 + m_2 + \dots + m_H = M$).
Beginning with the first hero, combatants take turns striking with their swords. A hero may strike any monster, while a monster may strike any hero (anywhere on the circle). A monster that takes $K$ strikes is destroyed. Heroes are invincible.
Task
The heroes are fighting for glory and wish to receive as few strikes as possible. What is the least number of strikes that the heroes must receive before destroying all the monsters?
Input data
The first line of input will contain the integers $H$ and $K$, separated by a space.
The second line will contain $H$ space-separated integers, $m_1$, $m_2$, ..., $m_H$.
Output data
Output a single integer, the minimum number of strikes that the heroes can receive.
Constraints and clarifications
- $1 \leq H \leq 3 \ 000$
- $1 \leq M \leq 1 \ 000 \ 000 \ 000$
- $1 \leq K \leq 1 \ 000$
- $0 \leq m_i \leq M$ for $1 \leq i \leq H$
- The answer is guaranteed not to exceed $10^{18}$.
| # | Points | Constraints |
|---|---|---|
| 0 | 0 | Examples |
| 1 | 7 | $H \leq 10$, $M \leq 4$, $K \leq 4$ |
| 2 | 11 | $H \leq 20$, $M \leq 10$, $K \leq 30$ |
| 3 | 15 | $M \leq 150 \ 000$ |
| 4 | 17 | $M \leq 5 \ 000 \ 000$ |
| 5 | 19 | $M \leq 30 \ 000 \ 000$ |
| 6 | 31 | No additional constraints |
Example 1
stdin
3 1 0 3 3
stdout
3
Explanation
There are $H=3$ heroes and $M=6$ monsters with $K=1$ life each. The initial order is HHMMMHMMM (where H is a hero and M is a monster). The first two heroes destroy the first two monsters. The third monster strikes. The third hero destroys the fourth monster. The last two monsters strike. The circle is now HHMHMM. The second time around, every hero destroys one monster and the heroes receive no further strikes.
Example 2
stdin
3 2 0 3 3
stdout
10