← 返回题目列表

Codeforces · 1974/E

E. 金钱能买到幸福

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

作为一名物理学家,查理喜欢用简单而精确的方式规划自己的生活。

在接下来的 $$$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 只在月底收到工资,因此无法承担任何费用。

在第二个测试用例中,查理在第一个月获得了免费的幸福。

在第三个测试用例中,查理在第二个月购买幸福是最佳的。即使最后剩下钱,查理也无法回到过去,获得第一个月的幸福。