Heroes

— 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}$.

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