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

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

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

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

В первой строке даны два целых числа n и b (1 ≤ n ≤ 105, 1 ≤ b ≤ 108) - количество минут, которое работает почта, и количество клонов, которых успевают обслужить за минуту.

Во второй строке даны n целых чисел ai (0 ≤ ai ≤ 108) - количество клонов, которые придут на почту в начале i-й минуты.

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

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