CF1697A Parkway Walk

你正穿过你家附近的一条林荫大道，道路上有 $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≤n≤100;1≤m≤104)$。 测试数据的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n(1≤a_i≤100)$，其中 $a_i$ 是编号为 $i$ 和 $i+1$ 的长椅之间的距离。

对于每个测试案例，输出一个整数——表示在相应的测试数据中，你必须恢复的最小能量（通过坐在长椅上），以便你从长椅 $1$ 到达长椅 $n+1$（并结束行走）。 ## 样例 #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 ```

在样例的第 $1$ 组测试数据中，你可以花费 $1$ 单位能量走到长椅 $2$，然后在长椅 $2$ 上坐下并恢复 $2$ 单位能量，再花费 $2$ 单位能量走到长椅 $3$，然后再恢复 $1$ 单位能量并走到长椅 $4$。 在样例的第 $3$ 组测试数据中，你有足够的能量直接走到长椅 $6$，根本不用坐下休息恢复能量。