Ксероксинатор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Доктору Хайнцу Фуфелшмерцу надоело стоять в очередях. Поэтому он создал ксероксинатор — устройство, создающее клонов людей. И теперь он отправляет своих клонов стоять в очередях вместо себя. К сожалению, в работе устройства произошел непредвиденный сбой. Теперь создается слишком много клонов Хайнца, и все они идут на почту.

Сегодня почта работает в течение $$$n$$$ минут, пронумерованных от $$$1$$$ до $$$n$$$. В начале $$$i$$$-й минуты на почту зайдет $$$a_i$$$ клонов Фуфелшмерца, и они встанут в конец очереди. За одну минуту на почте успевают обслужить не более $$$b$$$ клонов — если в очереди находятся хотя бы $$$b$$$ клонов, то обслуживают $$$b$$$ первых из них, а иначе обслуживают всех, кто стоит в очереди. Все клоны, обслуженные на $$$i$$$-й минуте, выйдут с почты в конце $$$i$$$-й минуты. В конце $$$n$$$-й минуты почта закроется. Все клоны, которых не успели обслужить, еще минуту постоят возмущаясь, и разойдутся. Помогите Хайнцу вычислить суммарное время пребывания всех клонов на почте.

Обратите внимание, что если клон зашел на почту в начале $$$i$$$-й минуты и вышел в конце $$$i$$$-й минуты, то он провел на почте одну минуту.

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$b$$$ — количество минут, которое работает почта, и количество клонов, которых успевают обслужить за минуту ($$$1 \le n \le 100\,000$$$, $$$1 \le b \le 10^8$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — количество клонов, которые придут на почту в начале $$$i$$$-й минуты ($$$0 \le a_i \le 10^8$$$).

Выходные данные

Выведите одно целое число — суммарное время, которое все клоны проведут на почте.

Пример

Входные данные
3 4
1 5 9
Выходные данные
22