N boxes are arranged in a row. Initially, the
ith box on the left contains
ai candies. Gromozeka chooses a box containing at least one candy, and eats one of the candies in the selected box. He can perform this action any number of times. His goal is to ensure that any two adjacent boxes contain no more than
x candies.
Find the minimum number of operations required to achieve Gromozeka's goal.
Input
The first line contains two numbers
N (
\(2<=N<=10^5\)) and
x ;(
\(0<=x<=10^9\)). The second line contains
N integers
ai (
\(0<=a_i<= 10^9\)).
Imprint
Output the answer to the problem.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
3 3
2 2 2
| 1 |
You must eat one candy in the second box. Then the number of candies in each box will be (2,1,2). |
| 2 |
6 1
1 6 1 2 0 4
| 11 |
For example, you can eat six candies in the second box, two in the fourth, and three in the sixth. Then the number of candies in each box will be (1,0,1,0,0,1). |
| 3 |
5 9
3 1 4 1 5
| 0 |
Goal already reached |
| 4 |
2 0
5 5 |
10 |
All candies must be eaten. |