시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB69543574.468%

문제

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

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

출력

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

예제 입력 1

3 4
1 5 9

예제 출력 1

22