Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

**[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 $h$. There are $n$ monsters. For $i$-th monster($1 \le i \le n$), it has damage health point $a_i$ and reward health point $b_i$.

If Harry chooses to fight the $i$-th monster ($1 \le i \le n$ ), his health point will decrease by $a_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 $i$-th monster, that monster releases a potion that increases Harry’s health point by $b_i$.

Harry can fight the monsters **in any order**.

Calculate the maximum number of fights Harry can win.

**Note That: for all** $i$ **(** $1 \le i \le n$ **),** $a_i \le b_i$

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

The first line of each test case contains two integers $n$ and $h$ $(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 $n$ integers $a_1,a_2,\ldots,a_n$ $(1 \le a_i \le 10^9)$ — damage health point for each monster.

The third line contains $n$ integers $b_1,b_2,\ldots,b_n$ $(1 \le b_i \le 10^9)$ — reward health point for each monster.

It is guaranteed that for all $i$ ($1 \le i \le n$), $a_i \le b_i$

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

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

Input | Output |
---|---|

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.

92% Solution Ratio

s_semicolonEarliest,

bisnu_sarkarFastest, 0.0s

prodip_bsmrstuLightest, 1.7 MB

hattiMattimTimShortest, 555B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.