405472: GYM101968 H Win Strategy

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Win Strategytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are at a programming contest where there will be $$$n$$$ problems. For each problem you know at what time it will be available for you to read (and solve). Also you know how much time you need to solve it.

To solve a problem, you need to spend the needed time continuously without switching between different problems.

Find the maximum number of problems you can solve in the given contest time.

Input

The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 250$$$), the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$L$$$ ($$$1 \le n, L \le 1000$$$), the number of problems and the length of the contest, respectively.

Each of the following $$$n$$$ lines contains two space-separated integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i}, b_{i} \le L$$$), which means the $$$i^{th}$$$ problem will be available at minute $$$a_{i}$$$ and you need $$$b_{i}$$$ minutes to solve it.

Problems will be given in a non-decreasing order of $$$a_{i}$$$.

Output

For each test case, output a single line with the maximum number of problems you can solve during the contest.

ExampleInput
1
4 10
1 3
1 2
1 6
2 2
Output
3

加入题单

上一题 下一题 算法标签: