您正在穿过您家附近的一条大道。公园道路上有一排 $$$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$$$ 根本不坐。