B. Doors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ doors. You want to open all of them. There are some rules.

At first, you can only open the first door. For each $$$i \ge 1$$$, you can open the $$$i+1$$$-th door only if you have already opened the $$$i$$$-th door.

Initially, you have $$$x$$$ coins. There is a lock on the $$$i$$$-th door with a cost of $$$c_i$$$. In other words, you need to spend $$$c_i$$$ coins to open the $$$i$$$-th door. If the number of coins you currently have is strictly less than $$$c_i$$$, you will not be able to open the $$$i$$$-th door. After opening the $$$i$$$-th door, you will receive $$$a_i$$$ coins as a prize.

You can do the following operation any number of times:

  • Choose an index $$$i$$$, where $$$1 \le i \le n$$$, and set $$$c_i$$$ to $$$0$$$.

Find the minimum number of operations necessary to open all the doors.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. For each test case:

  • The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le x \le 10^9$$$).
  • The second line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le 10^9$$$).
  • The third line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Output

For each test case, output the minimum number of operations needed to open all the doors.

Example
Input
3
1 1
1
1
3 10
9 6 5
1 1 1
3 10
5 9 9
1 2 9
Output
0
1
2
Note

In the first test case, you don't need to perform any operations. You can just spend $$$1$$$ coin to open the first (and only) lock.

In the second test case, you can first set $$$c_i$$$ to $$$0$$$. Then, you can do the following:

  • Open the first door. You spend $$$0$$$ coins and receive $$$1$$$ coin. After that, you have $$$11$$$ coins.
  • Open the second door. You spend $$$6$$$ coins and receive $$$1$$$ coin. After that, you have $$$6$$$ coins.
  • Open the third door. You spend $$$5$$$ coins and receive $$$1$$$ coin. After that, you have $$$2$$$ coins.