You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

在接下来的 $m$ 个月里，Charlie 从零开始，每月努力工作并赚取 $x$ 英镑。在第 $i$ 个月（$1 \le i \le m$），他有一次机会花费 $c_i$ 英镑来获得 $h_i$ 的幸福值。

不允许借钱。在第 $i$ 个月赚到的钱只能在之后的第 $j$ 个月（$j>i$）花费。

由于物理学家不会编程，请你帮 Charlie 求出他能获得的最大幸福值总和。

输入格式

输入的第一行包含一个整数 $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$ 个月的花费和可获得的幸福值。注意，有些幸福值可能是免费的（即某些 $c_i=0$）。

保证所有测试用例中 $\sum_i h_i$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，表示 Charlie 能获得的最大幸福值总和。

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

0
10
200
15
1
9
9

说明/提示

在第一个测试用例中，Charlie 只在月末拿到工资，因此无法购买任何东西。

在第二个测试用例中，Charlie 在第一个月获得了免费的幸福值。

在第三个测试用例中，最优策略是在第二个月购买幸福值。即使最后还有剩余的钱，Charlie 也无法回到过去获得第一个月的幸福值。