В ряд расположены
N ящиков. Изначально в
i-м ящике слева находится
ai конфет. Громозека выбирает ящик, содержащий хотя бы одну конфету, и съедает одну из конфет в выбранном ящике.Он может выполнять это действие любое количество раз. Его цель добиться того, чтобы в любых двух соседних коробках содержалось не более
x конфет.
Найдите минимальное количество операций, необходимых для достижения цели Громозеки.
Входные данные
В первом строке задается два числа
N (
\(2<=N<=10^5\)) и
x (
\(0<=x<=10^9\)). Во второй строке содержится
N целых чисел
ai (
\(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 |
Все конфеты должны быть съедены. |