200640: [AtCoder]ARC064 C - Boxes and Candies

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

Problem Statement

There are $N$ boxes arranged in a row. Initially, the $i$-th box from the left contains $a_i$ candies.

Snuke can perform the following operation any number of times:

  • Choose a box containing at least one candy, and eat one of the candies in the chosen box.

His objective is as follows:

  • Any two neighboring boxes contain at most $x$ candies in total.

Find the minimum number of operations required to achieve the objective.

Constraints

  • $2 ≤ N ≤ 10^5$
  • $0 ≤ a_i ≤ 10^9$
  • $0 ≤ x ≤ 10^9$

Input

The input is given from Standard Input in the following format:

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

Output

Print the minimum number of operations required to achieve the objective.


Sample Input 1

3 3
2 2 2

Sample Output 1

1

Eat one candy in the second box. Then, the number of candies in each box becomes $(2, 1, 2)$.


Sample Input 2

6 1
1 6 1 2 0 4

Sample Output 2

11

For example, eat six candies in the second box, two in the fourth box, and three in the sixth box. Then, the number of candies in each box becomes $(1, 0, 1, 0, 0, 1)$.


Sample Input 3

5 9
3 1 4 1 5

Sample Output 3

0

The objective is already achieved without performing operations.


Sample Input 4

2 0
5 5

Sample Output 4

10

All the candies need to be eaten.

Input

题意翻译

$N$个箱子横排成一列,左边第$i$个箱子里装着$a_i$个糖果。 Snuke可以多次执行以下操作: 选一个里面不少于$1$个糖果的箱子,从那个箱子里吃一个糖果。 他的目标: 任何$2$个相邻的箱子都不多于$x$个糖果。 请确定实现他的目标所需的最小操作次数。

加入题单

上一题 下一题 算法标签: