Ксероксинатор
Доктору Хайнцу Фуфелшмерцу набридло стояти в чергах, тому він винайшов ксероксинатор — пристрій, що створює клонів людей. Тепер він відправляє своїх клонів стояти в чергах замість себе. На жаль, пристрій дав збій, і тепер створюється надто багато клонів Хайнца, які всі йдуть на пошту.
Сьогодні пошта працює протягом 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-ї хвилини.
Вихідні дані
Виведіть одне ціле число — загальний час, який усі клони проведуть на пошті.