← 返回题目列表

Codeforces · 1697/A

A. 大道步行

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

您正在穿过您家附近的一条大道。公园道路上有一排 $$$n+1$$$ 长凳,从左到右编号为 $$$1$$$ 到 $$$n+1$$$。长凳 $$$i$$$ 和 $$$i+1$$$ 之间的距离为 $$$a_i$$$ 米。

最初,您拥有 $$$m$$$ 单位的能量。要行走 $$$1$$$ 米的距离,您会花费 $$$1$$$ 单位的能量。如果你没有精力,你就无法行走。另外,你可以通过坐在长凳上来恢复能量(这是恢复能量的唯一方法)。当你坐着时,你可以恢复任何你想要的整数能量(如果你坐的时间更长,你恢复的能量更多)。请注意,您的能量可能会超过 $$$m$$$。

你的任务是找到从长凳 $$$1$$$ 到达长凳 $$$n+1$$$ (并结束步行)所需恢复的最低能量(通过坐在长凳上)。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100$$$; $$$1 \le m \le 10^4$$$)。

测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$),其中 $$$a_i$$$ 是长凳 $$$i$$$ 和 $$$i+1$$$ 之间的距离。

输出

对于每个测试用例,打印一个整数 - 在相应的测试用例中,从长凳 $$$1$$$ 到达长凳 $$$n+1$$$(并结束步行)所需恢复的最小能量(通过坐在长凳上)。

示例

输入 #1

3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5

输出 #1

3
8
0

注意

在示例的第一个测试用例中,您可以走到长凳$$$2$$$,花费$$$1$$$单位能量,然后在第二个长凳上恢复$$$2$$$单位能量,走到长凳$$$3$$$,花费$$$2$$$单位能量,恢复$$$1$$$单位能量并转到长凳$$$4$$$。

在示例的第三个测试用例中,您有足够的精力直接走到长凳上 $$$6$$$ 根本不坐。