J. John Buck Legends
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The problemsetters of the Gennady Needs Your Rating contest have written $$$n$$$ problems, but they forgot that they still have to write solutions! You know that for the $$$i$$$-th problem, it takes them $$$a_i$$$ minutes to write a correct solution and $$$b_i$$$ minutes to write an incorrect solution.

You know that the problemsetters will write exactly one solution for each problem and spend at most $$$k$$$ minutes in total writing solutions for all problems. For how many problems is it possible that the problemsetters write a correct solution?

More formally, count the number of values $$$i$$$ among $$$1, 2, \ldots, n$$$ such that there exists some arrangement of correct and incorrect solutions for each problem, where a correct solution is written for problem $$$i$$$, and the total time spent writing all solutions does not exceed $$$k$$$. Note that the arrangements may differ for different values of $$$i$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le k \le 10^9$$$) — the number of problems and the maximum amount of time spent, respectively.

The next $$$n$$$ lines each contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^4$$$) — the times needed to write a correct solution and an incorrect solution, respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Additional constraint on the input: there exists some arrangement of correct and incorrect solutions such that all solutions are written in at most $$$k$$$ minutes.

Output

For each test case, output a single integer — the number of problems that might have a correct solution.

Example
Input
3
5 20
6 7
15 5
6 5
100 1
2 1
1 1
2 1
3 8
2 1
3 2
4 5
Output
3
0
3
Note

In the first test case, problems $$$1$$$, $$$3$$$, and $$$5$$$ might have a correct solution. For example,

  • Writing correct solutions to problems $$$1$$$ and $$$5$$$ and incorrect solutions to everything else takes $$$6 + 5 + 5 + 1 + 2 = 19$$$ minutes.
  • Writing a correct solution to problem $$$3$$$ and incorrect solutions to everything else takes $$$7 + 5 + 6 + 1 + 1 = 20$$$ minutes.

In the second test case, it is not possible to write the correct solution since writing the correct solution takes $$$2$$$ minutes and $$$k = 1$$$.