28656번 - Ксероксинатор 다국어

문제

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

Сегодня почта работает в течение $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$).

출력

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

제한

힌트