Олимпиадный тренинг

Задача . Конфеты и коробки


В ряд расположены N ящиков. Изначально в i-м ящике слева находится ai конфет.  Громозека выбирает ящик, содержащий хотя бы одну конфету, и съедает одну из конфет в выбранном ящике.Он может выполнять это действие любое количество раз. Его цель добиться того, чтобы в любых двух соседних коробках содержалось не более x конфет.
Найдите минимальное количество операций, необходимых для достижения цели Громозеки.

Входные данные
В первом строке задается два числа N (\(2<=N<=10^5\)) и (\(0<=x<=10^9\)).  Во второй строке содержится N целых чисел a(\(0<=a_i<=10^9\)).

Выходные данные
Выведите ответ на задачу.

 

Примеры
Входные данные Выходные данные Пояснения
1 3 3
2 2 2
1 Необходимо съесть одну конфету во второй коробке. Тогда количество конфет в каждой коробке станет (2,1,2).
2 6 1
1 6 1 2 0 4
11 Например, можно съесть шесть конфет во второй коробке, две в четвертой и три в шестой. Тогда количество конфет в каждой коробке станет (1,0,1,0,0,1).
3 5 9
3 1 4 1 5
0 Цель уже достигнута
4 2 0
5 5
10 Все конфеты должны быть съедены.

 




time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Mingw-w642
Python1
Комментарий учителя