Problem Description

Little A has \( n \) candy boxes, with the \( i \)-th box containing \( a_i \) candies.

Little A can eat one candy from any box at a time. He wants to know the minimum number of candies he needs to eat so that the sum of candies in any two adjacent boxes does not exceed \( x \).

Input Format

The first line contains two integers separated by a space, representing the number of candy boxes \( n \) and the given parameter \( x \).

The second line contains \( n \) integers separated by spaces, where the \( i \)-th integer represents the number of candies \( a_i \) in the \( i \)-th box.

Output Format

Output a single integer representing the minimum number of candies that need to be eaten.

Sample Input and Output

Sample Input #1

3 3
2 2 2

Sample Output #1

1

Sample Input #2

6 1
1 6 1 2 0 4

Sample Output #2

11

Sample Input #3

5 9
3 1 4 1 5

Sample Output #3

0

Notes

Explanation of Sample Input and Output #1

Eating one candy from the second box is sufficient.

Explanation of Sample Input and Output #2

Eat 6 candies from the second box, 2 candies from the fourth box, and 3 candies from the sixth box.

Data Size and Constraints

• For 30% of the data, \( n \leq 20 \), \( a_i, x \leq 100 \).
• For 70% of the data, \( n \leq 10^3 \), \( a_i, x \leq 10^5 \).
• For 100% of the data, \( 2 \leq n \leq 10^5 \), \( 0 \leq a_i, x \leq 10^9 \).

见题面 Input 部分

见题面 Output 部分