Problem

Chef came across a new online judge that has N problems, and decided that he wants to solve them.

Table of Contents

Chef takes Ai consecutive minutes to solve the i-th problem, and will take a break of Bi minutes immediately after solving it.
That is, Chef will solve a problem, then take a break. Solve another problem, then take another break, and so on.

Chef has K minutes of free time. If he chooses the problems and their order optimally, what is the maximum number of problems he can solve in this time?

Note that a problem is considered solved if Chef finishes solving it by the K-th minute, even if the break time of the last problem extends past minute K. See the sample tests below for an example.

Input Format

The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of three lines of input.
- The first line of each test case contains two space-separated integers N and K — the number of problems in the online judge and Chef’s free time, respectively.
- The second line of each test case contains space-separated integers — the values 1,2,…,A1,A2,…,AN.
- The third line of each test case contains N space-separated integers — the values 1,2,…,B1,B2,…,BN.

Output Format

For each test case, output on a new line the maximum number of problems that Chef can solve within K minutes.

Constraints

1≤T≤2⋅104
1≤N≤2⋅105
1≤K≤108
1≤Ai≤108
0≤Bi≤108
The sum of N over all test cases won’t exceed 2⋅1052⋅105.

Sample 1:

Input

Output

4
3 10
3 4 5
2 4 2
3 8
3 4 5
2 4 2
5 20
23 54 124 54 83
2 9 5 2 10
5 20
4 7 12 34 13
30 4 3 0 9

Explanation:

Test case 11: Chef can solve the first problem followed by the second problem.

33 minutes for the first problem
22 minutes of break time after solving it, for a total of 55 minutes
55 minutes for the third problem, for a total of 1010 minutes
There’s one minute of break time left which goes beyond 1010 minutes, but that’s ok: Chef finished solving 22 problems within 1010 minutes.

Test case 22: The same times as the first sample, but with �=8K=8. Now, Chef can solve any one problem, but cannot solve a second one no matter what.

Test case 33: Chef can’t solve anything within 2020 minutes.

Test case 44: Chef can solve the third problem followed by the first problem.