— Ionele, îți irosești viața cu jocurile pe calculator! — Nu-i nimic, Mami, mai am trei vieți rămase!
În Marea Bătălie pentru a salva tot binele din lume, $H$ eroi se luptă cu o gașcă de $M$ monștri. Luptătorii stau în cerc într-o anumită ordine. După al $i$-lea erou în cerc se află $m_i$ monștri (respectiv $m_1 + m_2 + \dots + m_H = M$).
Începând cu primul erou, fiecare luptător atacă cu sabia sa. Un erou poate lovi orice monstru, iar un monstru poate lovi orice erou. Dacă un monstru e lovit de $K$ ori acesta moare. Eroii sunt invincibili.
Cerință
Eroii se luptă pentru glorie și doresc să fie loviți cât mai puțin posibil. Care este numărul minim de lovituri pe care îl vor primi eroii până vor răpune toți monștrii?
Date de intrare
Prima linie de intrare va conține numerele $H$ și $K$, separate prin spațiu.
A doua linie va conține $H$ numere separate prin spațiu, $m_1$, $m_2$, ..., $m_H$.
Date de ieșire
Prima linie va conține o singură valoare care va reprezenta numărul minim de lovituri pe care le vor primi eroii.
Restricții și precizări
- $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$ pentru $1 \leq i \leq H$
- Este garantat că răspunsul nu va depăși $10^{18}$.
| # | Punctaj | Restricții |
|---|---|---|
| 0 | 0 | Exemplele |
| 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 | Fără restricții suplimentare |
Exemplul 1
stdin
3 1 0 3 3
stdout
3
Explicație
Sunt $H=3$ eroi și $M=6$ monștri, fiecare cu $K=1$ puncte de viață. Ordinea inițială este HHMMMHMMM (unde H este un erou iar M este un monstru). Primii doi eroi omoară primii doi monștri. Al treilea monstru atacă. Al treilea erou omoară al patrulea monstru. Ultimii doi monștri atacă. Cercul acum e HHMHMM. În a doua rundă, fiecare erou lovește un monstru și niciun erou nu este lovit.
Exemplul 2
stdin
3 2 0 3 3
stdout
10