← 返回题目列表

AtCoder · arc064_a

C. 盒子和糖果

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 盒子排列成一排。 最初, i左边第一个框包含 a_i 糖果。

Snuke 可以执行任意多次以下操作:

  • 选择一个至少装有一颗糖果的盒子,然后吃掉所选盒子中的一颗糖果。

他的目标如下:

  • 任何两个相邻的盒子最多包含 总共 x 糖果。

找出实现目标所需的最少操作数。

约束

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

输入

输入由标准输入按以下格式给出:

N x
a_1 a_2 ... a_N

输出

打印实现目标所需的最少操作数。


示例输入 1

3 3
2 2 2

示例输出 1

1

吃第二个盒子里的一颗糖果。 那么每个盒子里的糖果数量就变成了 (2, 1, 2).


示例输入 2

6 1
1 6 1 2 0 4

示例输出 2

11

例如,吃第二个盒子里的六颗糖果,第四个盒子里的两颗糖果,第六个盒子里的三颗糖果。 那么每个盒子里的糖果数量就变成了 (1, 0, 1, 0, 0, 1).


示例输入 3

5 9
3 1 4 1 5

示例输出 3

0

无需执行操作即可实现目标。


示例输入 4

2 0
5 5

示例输出 4

10

所有糖果都需要吃掉。