作为一名物理学家,查理喜欢用简单而精确的方式规划自己的生活。
在接下来的 $$$m$$$ 个月里,从没有钱开始,查理将努力工作,每月赚取 $$$x$$$ 英镑。对于第 $$$i$$$ 个月 $$$(1 \le i \le m)$$$,将有一次支付成本 $$$c_i$$$ 英镑来获得幸福 $$$h_i$$$ 的机会。
不允许借用。第 $$$i$$$ 个月赚到的钱只能在随后的第 $$$j$$$ 个月中花费 ($$$j>i$$$)。
由于物理学家不编码,请帮助查理找到可获得的最大幸福总和。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数,$$$m$$$ 和 $$$x$$$ ($$$1 \le m \le 50$$$, $$$1 \le x \le 10^8$$$)——总月数和月薪。
以下 $$$m$$$ 行中的第 $$$i$$$ 包含两个整数,$$$c_i$$$ 和 $$$h_i$$$ ($$$0 \le c_i \le 10^8$$$, $$$1 \le h_i \le 10^3$$$) - 第 $$$i$$$ 提供的成本和幸福感月。请注意,有些幸福可能是免费的(对于某些 $$$i$$$ 来说 $$$c_i=0$$$)。
保证所有测试用例的 $$$\sum_i h_i$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数,查理可以获得的最大幸福感。
示例
输入 #1
7 1 10 1 5 2 80 0 10 200 100 3 100 70 100 100 200 150 150 5 8 3 1 5 3 3 4 1 5 5 3 2 5 1 5 2 1 5 3 2 5 2 4 4 1 5 1 3 4 5 2 2 1 1 2 3 5 3 2 3 2
输出 #1
0 10 200 15 1 9 9
注意
在第一个测试用例中,Charlie 只在月底收到工资,因此无法承担任何费用。
在第二个测试用例中,查理在第一个月获得了免费的幸福。
在第三个测试用例中,查理在第二个月购买幸福是最佳的。即使最后剩下钱,查理也无法回到过去,获得第一个月的幸福。