Fall with Full Star

Fall loves playing games and collecting strange achievements in games. If he doesn't pass a level with full stars, he will feel uncomfortable.

Today, Fall is playing a new game. The game includes $n$ levels without order, which means you can play the levels in any order. However, each level can only be challenged once. During the challenge, Fall may get hurt or pick up rare items. Assuming that before he challenges level $i$, he has power $x$, and after he challenges this level, his power will be increased by $d_i$. After that, if his power is higher than or equal to $s_i$, he will get a full star in this level.

Initially, Fall has power $s_0$ , he wants to find a challenge order that he can get full star levels as more as possible.

The first line contains a single integer T ($1\leq T \leq 20$), the number of test cases. For each test case:

The first line contains two integers $n,s_0(1\leq n\leq 1\times 10^5,\sum{n}\leq 10^6, |s_0|\leq 10^{14})$.

The $i$-th line of the next $n$ lines contains two integers $d_i,s_i(|d_i|\leq 10^9,|s_i|\leq 10^{14})$, representing the information about the $i$-th level.

For each test case, output a single line containing one integer -- the maximum number of full star levels that Fall can get in a single line.

1
3 0
4 5
2 5
1 100

2

2022“杭电杯”中国大学生算法设计超级联赛（4）