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

To destroy humanity, The Monster Association sent $$$n$$$ monsters to Earth's surface. The $$$i$$$-th monster has health $$$h_i$$$ and power $$$p_i$$$.

With his last resort attack, True Spiral Incineration Cannon, Genos can deal $$$k$$$ damage to all monsters alive. In other words, Genos can reduce the health of all monsters by $$$k$$$ (if $$$k > 0$$$) with a single attack.

However, after every attack Genos makes, the monsters advance. With their combined efforts, they reduce Genos' attack damage by the power of the $$$^\dagger$$$weakest monster $$$^\ddagger$$$alive. In other words, the minimum $$$p_i$$$ among all currently living monsters is subtracted from the value of $$$k$$$ after each attack.

$$$^\dagger$$$The Weakest monster is the one with the least power.

$$$^\ddagger$$$A monster is alive if its health is strictly greater than $$$0$$$.

Will Genos be successful in killing all the monsters?

Input

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

The first line of each test case contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^5$$$) — the number of monsters and Genos' initial attack damage. Then two lines follow, each containing $$$n$$$ integers describing the arrays $$$h$$$ and $$$p$$$ ($$$1 \le h_i, p_i \le 10^9$$$).

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

Output

For each test case, print the answer — "YES" (without quotes) if Genos could kill all monsters and "NO" otherwise.

Example
Input
3
6 7
18 5 13 9 10 1
2 7 2 1 2 6
3 4
5 5 5
4 4 4
3 2
2 1 3
1 1 1
Output
YES
NO
YES
Note

In the first example, after Genos' first attack, $$$h$$$ and $$$k$$$ will update to:

  • $$$h: [11,0,6,2,3,0]$$$
  • $$$k: 7-1 = 6$$$
After second attack:
  • $$$h: [5,0,0,0,0,0]$$$
  • $$$k: 6-2 = 4$$$
After third attack:
  • $$$h: [1,0,0,0,0,0]$$$
  • $$$k: 4-2 = 2$$$
After fourth attack:
  • $$$h: [0,0,0,0,0,0]$$$
As Genos could kill all monsters, the answer is YES.