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