题目描述

你正穿过你家附近的一条林荫大道，道路上有 $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$，根本不用坐下休息恢复能量。

样例

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

3
8
0