Heroes (RMI contest)
Time limit: 0.4 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: arithmetic, large number arithmetic, number theory, greedy

# Heroes

Time limit: *400 ms*
Memory limit: *256 MB*

> — 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 + ... + 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.

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?

## Standard input

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.

## Standard output

Output a single integer, the minimum number of strikes that the heroes can receive.

## Constraints and notes

* 1 <= H <= 3,000;
* 1 <= M <= 1,000,000,000;
* 1 <= K <= 1,000;
* 0 <= m_i <= M for 1 <= i <= H;
* The answer is guaranteed not to exceed 10^18.

| # | Points | Restrictions              |
|---|--------|---------------------------|
| 1 | 7      | H <= 10, M <= 4, K <= 4   |
| 2 | 11     | H <= 20, M <= 10, K <= 30  |
| 3 | 15     | M <= 150,000              |
| 4 | 17     | M <= 5,000,000            |
| 5 | 19     | M <= 30,000,000           |
| 6 | 31     | No further constraints.   |

---

**Example 1:**

*Input:*
```
3 1
0 3 3
```
*Output:*
```
3
```

---

**Example 2:**

*Input:*
```
3 2
0 3 3
```
*Output:*
```
10
```

---

### Explanations

In the first example there are H = 3 heroes and M = 6 monsters with K = 1 life each. The initial order is **HHMMMHMMM** (where **H** = hero, **M** = 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.

Starter code:

Grader code:

Setup script:

Evaluation script: