Problem
Chef came across a new online judge that has N problems, and decided that he wants to solve them.
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
2 1 0 2
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.