Solve More Problems! CodeChef Solution

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 $N$ 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

Sample 1:

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 $1$: Chef can solve the first problem followed by the second problem.

• $3$ minutes for the first problem
• $2$ minutes of break time after solving it, for a total of $5$ minutes
• $5$ minutes for the third problem, for a total of $10$ minutes
• There’s two minutes of break time left which goes beyond $10$ minutes, but that’s ok: Chef finished solving $2$ problems within $10$ minutes.

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

Test case $3$: Chef can’t solve anything within $20$ minutes.

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