Ваня измельчает картофель в вертикальном кухонном комбайне. В любой момент времени в комбайне помещается количество картофеля высоты не более h, при этом комбайн измельчает k сантиметров картофеля за секунду. Если картофеля в комбайне меньше k сантиметров, то за данную секунду комбайн измельчает весь оставшийся в нём картофель.
У Вани есть n картофелин, высота i-й из которых равна ai. Он поочередно засовывает в комбайн картофелины, начиная с картофелины номер 1 и заканчивая картофелиной номер n. Формально, каждую секунду происходит следующее:
- Если у Вани ещё остались картофелины, то он последовательно засовывает их в комбайн, пока там не кончится место.
- Комбайн измельчает k сантиметров картофеля (или просто всё, что есть в комбайне).
По имеющейся информации о параметрах комбайна и картофелин вычислите, за какое время весь картофель будет измельчён.
Выходные данные
Выведите одно целое число — количество секунд, которые потребуются на измельчение всего имеющегося картофеля.
Примечание
Рассмотрим первый пример.
- Сначала Ваня засовывает в комбайн картофелину высотой 5. Через одну секунду в комбайне остаётся картофель высотой 2.
- Теперь Ваня засовывает картофелину высотой 4, и через секунду там остаётся количество картофеля высоты 3.
- Ваня засовывает картофель высотой 3, через секунду там снова столб картофеля высотой 3.
- Ваня засовывает картофелины высотой 2 и 1, через секунду опять остаётся количество картофеля высоты 3.
- На этой секунде комбайн измельчает весь оставшийся картофель и завершает свою работу.
Во втором примере Ваня засовывает в комбайн картофелину высотой 5 и ждёт две секунды, чтобы она полностью измельчилась. Аналогично для 4 следующих картофелин. Итого потребуется 2·5 = 10 секунд.
В третьем примере Ваня сразу засовывает в комбайн весь имеющийся картофель и ждёт 2 секунды.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 3
5 4 3 2 1
|
5
|
|
2
|
5 6 3
5 5 5 5 5
|
10
|
|
3
|
5 6 3
1 2 1 1 1
|
2
|