В офис привезли новые блокноты на 2021-й год. Яна написала всем сотрудникам, что блокнот можно получить у нее в кабинете лично в руки. И к ней в кабинет поспешили все сотрудники офиса.

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

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

Формат входных данных

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

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

Формат выходных данных

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

Пример