Ксероксинатор
Доктору Хайнцу Фуфелшмерцу надоело стоять в очередях. Поэтому он создал ксероксинатор устройство, создающее клонов людей. И теперь он отправляет своих клонов стоять в очередях вместо себя. К сожалению, в работе устройства произошел непредвиденный сбой. Теперь создается слишком много клонов Хайнца, и все они идут на почту.
Сегодня почта работает в течение n минут, пронумерованных от 1 до n. В начале i-й минуты на почту зайдет a[i] клонов Фуфелшмерца, и они встанут в конец очереди. За одну минуту на почте успевают обслужить не более b клонов - если в очереди находятся хотя бы b клонов, то обслуживают b первых из них, а иначе обслуживают всех, кто стоит в очереди. Все клоны, обслуженные на i-й минуте, выйдут с почты в конце i-й минуты. В конце n-й минуты почта закроется. Все клоны, которых не успели обслужить, еще минуту постоят возмущаясь, и разойдутся. Помогите Хайнцу вычислить суммарное время пребывания всех клонов на почте.
Обратите внимание, что если клон зашел на почту в начале i-й минуты и вышел в конце i-й минуты, то он провел на почте одну минуту.
Входные данные
В первой строке даны два целых числа n и b (1 ≤ n ≤ 10^5, 1 ≤ b ≤ 10^8) - количество минут, которое работает почта, и количество клонов, которых успевают обслужить за минуту.
Во второй строке даны n целых чисел a[i] (0 ≤ a[i] ≤ 10^8) - количество клонов, которые придут на почту в начале i-й минуты.
Выходные данные
Выведите одно целое число - суммарное время, которое все клоны проведут на почте.