Description

题目描述

作为一名物理学家，$panda$喜欢用简单精确的语言来规划自己的生活。

在接下来的 $m$ 个月里，从没有钱开始，$panda$将努力工作，每月赚取 $x$ 英镑。在 $(1 \le i \le m)$ 月的 $i$ 个月里，将有一次机会，付出 $c_i$ 英镑的代价，获得 $h_i$ 的幸福。

不允许借贷。在 $i$ 月赚到的钱只能在之后的 $j$ 月( $j>i$ )花掉。

既然物理学家不会写代码，那就帮$panda$找出幸福的最大值吧。

输入格式

第一行输入包含一个整数 $t$ ( $1 \le t \le 1000$ ) - 测试用例数。

每个测试用例的第一行包含两个整数 $m$ 和 $x$ ( $1 \le m \le 50$ , $1 \le x \le 10^8$ )--总月数和月薪。

下面 $m$ 行的 $i$ -th包含两个整数： $c_i$ 和 $h_i$ ( $0 \le c_i \le 10^8$ ， $1 \le h_i \le 10^3$ )-- $i$ -月的费用和幸福。请注意，有些幸福可能是免费的( $c_i=0$ 为某些 $i$ 的幸福)。

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

输出格式

为每个测试案例打印一个整数，即查理能获得的最大幸福总和。

输入输出样例 #1

输入 #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

说明/提示

在第一个测试案例中，查理只能在月底拿到工资，因此无力支付任何费用。

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

在第三个测试案例中，查理最好在第二个月购买幸福。即使最后还有钱，查理也无法回到过去获得第一个月提供的幸福。

$30 \%$的数据，$1 \le m \le 10，1 \le x,c_i,h_i \le 10$

$50 \%$的数据，$1 \le m \le 50，1 \le x,c_i,h_i \le 10^3$

$100 \%$的数据，$1 \le m \le 50，1 \le x,c_i \le 10^8 ,1\le h_i \le 10^3$

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