Description

Xiao A has $n$ candy boxes; the $i$-th box contains $a_i$ candies.

Each time, Xiao A can eat one candy from one box. He wants to know: to make the sum of candies in any two adjacent boxes no greater than $x$, what is the minimum number of candies he must eat.

Input Format

The first line contains two space-separated integers, the number of boxes $n$ and the given parameter $x$.

The second line contains $n$ space-separated integers; the $i$-th integer is $a_i$, the number of candies in the $i$-th box.

Output Format

Output one line with a single integer, the minimum number of candies to eat.

3 3
2 2 2

1

6 1
1 6 1 2 0 4

11

5 9
3 1 4 1 5

0

Hint

Explanation for Sample Input/Output 1

Eating one candy from box 2 suffices.

Explanation for Sample Input/Output 2

Eat $6$ from box 2, $2$ from box 4, and $3$ from box 6.

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n \leq 20$ and $a_i, x \leq 100$.
• For $70\%$ of the testdata, it is guaranteed that $n \leq 10^3$ and $a_i, x \leq 10^5$.
• For $100\%$ of the testdata, it is guaranteed that $2 \leq n \leq 10^5$ and $0 \leq a_i, x \leq 10^9$.

Translated by ChatGPT 5