Limits 1s, 512 MB

[1 and 2 are completely different problems. Consider reading both.]

Harry and Hermione are in a fight with the monsters. But Hermione is currently busy with Ron. So Harry is fighting alone.

Harry has initial health point hh. There are nn monsters. For ii-th monster(1in1 \le i \le n), it has damage health point aia_i and reward health point bib_i.

If Harry chooses to fight the ii-th monster (1in1 \le i \le n ), his health point will decrease by aia_i.

Harry will win against a monster if and only if, his (Harry) health point is non-negative during the fight. Once Harry loses a fight, then he cannot fight any other monster.

If Harry wins against ii-th monster, that monster releases a potion that increases Harry’s health point by bib_i.

Harry can fight the monsters in any order.

Calculate the maximum number of fights Harry can win.

Note That: for all ii ( 1in1 \le i \le n ), aibia_i \le b_i

Input

The first line of the input contains a single integer t(1t10)t (1\le t \le 10 ) — the number of test cases.

The first line of each test case contains two integers nn and hh (1n2×105;1h109)(1 \le n \le 2 \times 10^5 ; 1 \le h \le 10^9)— the number of monsters and initial health point of Harry respectively.

The second line contains nn integers a1,a2,,ana_1,a_2,\ldots,a_n  (1ai109)(1 \le a_i \le 10^9) — damage health point for each monster.

The third line contains  nn integers b1,b2,,bnb_1,b_2,\ldots,b_n  (1bi109)(1 \le b_i \le 10^9) — reward health point for each monster.

It is guaranteed that for all ii (1in1 \le i \le n), aibia_i \le b_i

It is guaranteed that the sum of nn over all test cases does not exceed 2×1052 \times 10^5.

Output

For each test case, print a single integer — maximum number of fights Harry can win.

Sample

InputOutput
3
3 10
6 3 4
7 5 8
3 3
8 3 4
9 5 6
2 3
3 5
4 6
3
2
1

Explanation of test case 1:

Initial health point of Harry is 10.

Harry chooses to fight with the 1st monster. During the fight his health point becomes 4. So Harry win that fight. Then 1st monster release potion and Harry’s health point becomes 11.

Then Harry chooses to fight with the 2nd monster. In that fight Harry wins and his health point becomes 13.

Then Harry chooses to fight with the 3rd monster. In that fight Harry wins and his health point becomes 17.

So Harry can win all three fights.

Explanation of test case 2:

Initial health point of Harry is 3.

Harry chooses to fight the 2nd monster. Harry wins in that fight and his health point becomes 5.

Then Harry chooses to fight the 3rd monster. Harry wins in that fight and his health point becomes 7.

Then Harry chooses to fight the 1st monster. Unfortunately Harry losses that fight because Harry’s health point becomes -1 during the fight.

So Harry can win at most two fights.

Explanation of test case 3:

Initial health point of Harry is 3.

Harry chooses to fight the 1st monster. Harry wins in that fight and his health point becomes 4.

Then Harry chooses to fight the 2nd monster. Unfortunately Harry losses that fight because Harry’s health point becomes -1 during the fight.

So Harry can win at most one fight.

Submit

Login to submit.

Statistics

93% Solution Ratio
s_semicolonEarliest, Mar '22
user.075408Fastest, 0.0s
ShattajitLightest, 7.6 kB
mdshadeshShortest, 370B
Toph uses cookies. By continuing you agree to our Cookie Policy.