← 返回题目
题库练习 分礼品
← 上一题 下一题 →

A71412 | 分礼品

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

某班开联欢晚会，晓楠同学随机将若干礼品分成了 n 堆，第 i 堆有 Ai 个礼品。

班主任王老师看了晓楠同学分礼品的情况后，提出了一个要求：要求任意两堆相邻礼品的数量和不能超过 t ，如果超过了，就要从分好的礼品中拿出一部分。

请问：晓楠同学最少要从分好的礼品中，拿出多少个礼品，才能使得相邻的礼品的数量和满足老师说的要求？

输入格式

第1行，输入整数 n 和 t。

第2行，输入 n 个整数。

1≤n≤105，1≤t,Ai≤109。

输出格式

输出最少要拿出的礼品的数量。

输入输出样例

输入 #1
3 5
4 3 3
输出 #1
2
输入 #2
3 3
5 1 4
输出 #2
4
C++ 编辑器
输入
输出