题目描述

有 $N$ 个箱子横向排列成一排。最初，从左到右第 $i$ 个箱子中有 $a_i$ 个糖果。

你可以进行如下操作任意多次：

• 选择一个至少有 $1$ 个糖果的箱子，从中吃掉 $1$ 个糖果。

你的目标如下：

• 对于任意相邻的两个箱子，它们中糖果的总数都不超过 $x$。

请你求出，为了达成目标，所需操作次数的最小值。

输入格式

输入以如下格式从标准输入给出。

$N$ $x$ $a_1$ $a_2$ $...$ $a_N$

输出格式

输出为达成目标所需的最小操作次数。

样例 1

输入

3 3
2 2 2

输出

1

样例 2

输入

6 1
1 6 1 2 0 4

输出

11

样例 3

输入

5 9
3 1 4 1 5

输出

0

样例 4

输入

2 0
5 5

输出

10

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $0 \leq a_i \leq 10^9$
• $0 \leq x \leq 10^9$

样例解释 1

只需吃掉第 $2$ 个箱子的 $1$ 个糖果。这样，每个箱子的糖果数变为 $(2, 1, 2)$。

样例解释 2

例如，可以吃掉第 $2$ 个箱子的 $6$ 个糖果，第 $4$ 个箱子的 $2$ 个糖果，第 $6$ 个箱子的 $3$ 个糖果。这样，每个箱子的糖果数变为 $(1, 0, 1, 0, 0, 1)$。

样例解释 3

一开始就已经满足目标，无需进行任何操作。

样例解释 4

必须吃掉所有的糖果。

由 ChatGPT 4.1 翻译