LG#P3817. 小 A 的糖果

小 A 的糖果

P3817 小 A 的糖果

题目描述

\hspace{15pt}小 A 有 nn 个糖果盒,第 ii 个盒中有 aia_i 颗糖果。

\hspace{15pt}小 A 每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中糖的个数之和都不大于 xx,至少得吃掉几颗糖。

输入格式

\hspace{15pt}第一行输入两个整数 $n, x \left(2 \leqq n \leqq 10^5;\ 0 \leqq x \leqq 10^9\right)$ 代表糖果盒的个数和给定的参数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 10^9\right)$,其中 aia_i 代表第 ii 个盒子中的糖果个数。

输出格式

\hspace{15pt}在一行上输出一个整数,代表最少需要吃掉的糖果数量。

测试样例

3 3
2 2 2
1

样例 1 解释

\hspace{15pt}吃掉第 22 盒中的一颗糖果即可,此时三盒糖果的个数依次为 2,1,22, 1, 2,任意相邻两盒糖果个数之和都不超过 33。

6 1
1 6 1 2 0 4
11

样例 2 解释

\hspace{15pt}第 22 盒吃掉 66 颗,第 44 盒吃掉 22 颗,第 66 盒吃掉 33 颗,共吃掉 6+2+3=116+2+3=11 颗。此时各盒糖果的个数依次为 1,0,1,0,0,11, 0, 1, 0, 0, 1,任意相邻两盒糖果个数之和都不超过 11。

5 9
3 1 4 1 5
0

数据范围与提示

\hspace{15pt}对于 30%30\% 的数据,保证 n≦20n \leqq 20,ai,x≦100a_i, x \leqq 100。

\hspace{15pt}对于 70%70\% 的数据,保证 n≦103n \leqq 10^3,ai,x≦105a_i, x \leqq 10^5。

\hspace{15pt}对于 100%100\% 的数据,保证 2≦n≦1052 \leqq n \leqq 10^5,0≦ai,x≦1090 \leqq a_i, x \leqq 10^9。