311026: CF1923B. Monsters Attack!

B. Monsters Attack!time limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are playing a computer game. The current level of this game can be modeled as a straight line. Your character is in point $0$ of this line. There are $n$ monsters trying to kill your character; the $i$-th monster has health equal to $a_i$ and is initially in the point $x_i$.

Every second, the following happens:

• first, you fire up to $k$ bullets at monsters. Each bullet targets exactly one monster and decreases its health by $1$. For each bullet, you choose its target arbitrary (for example, you can fire all bullets at one monster, fire all bullets at different monsters, or choose any other combination). Any monster can be targeted by a bullet, regardless of its position and any other factors;
• then, all alive monsters with health $0$ or less die;
• then, all alive monsters move $1$ point closer to you (monsters to the left of you increase their coordinates by $1$, monsters to the right of you decrease their coordinates by $1$). If any monster reaches your character (moves to the point $0$), you lose.

Can you survive and kill all $n$ monsters without letting any of them reach your character?

Input

The first line of the input contains one integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$; $1 \le k \le 2 \cdot 10^9$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$);
• the third line contains $n$ integers $x_1, x_2, \dots, x_n$ ($-n \le x_1 < x_2 < x_3 < \dots < x_n \le n$; $x_i \ne 0$).

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, print YES if you can kill all $n$ monsters before they reach your character, or NO otherwise.

You can output each letter of the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will all be recognized as positive responses.

ExampleInput

5
3 2
1 2 3
-1 2 3
2 1
1 1
-1 1
4 10
3 4 2 5
-3 -2 1 3
5 3
2 1 3 2 5
-3 -2 3 4 5
2 1
1 2
1 2

Output

YES
NO
YES
YES
NO

Note

In the first example, you can act as follows:

• during the $1$-st second, fire $1$ bullet at the $1$-st monster and $1$ bullet at the $3$-rd monster. Then the $1$-st monster dies, the $2$-nd and the $3$-rd monster move closer;
• during the $2$-nd second, fire $2$ bullets at the $2$-nd monster. Then the $2$-nd monster dies, the $3$-rd monster moves closer;
• during the $3$-rd second, fire $2$ bullets at the $3$-rd monster. Then the $3$-rd monster dies.

In the second example, you can fire only $1$ bullet, so you can kill only one of the two monsters during the $1$-st second. Then, the remaining monster moves closer and kills your character.

题目大意：你正在玩一个电脑游戏，当前的游戏关卡可以看作一条直线，你的角色位于这条直线的点0处。有n个怪物试图杀死你的角色；第i个怪物有a_i的生命值，最初位于点x_i。

每秒钟发生以下事情：
1. 首先，你向怪物发射最多k颗子弹。每颗子弹瞄准一个怪物，并减少其1点生命值。你可以任意选择每颗子弹的目标（例如，你可以把所有子弹都射向一个怪物，射向不同的怪物，或者选择其他任何组合）。无论怪物的位置和其他任何因素，任何怪物都可以成为子弹的目标；
2. 然后，所有生命值为0或更少的怪物死亡；
3. 然后，所有存活的怪物向你的方向移动1个点（你左边的怪物增加其坐标，你右边的怪物减少其坐标）。如果任何怪物到达你的角色（移动到点0），你将失败。

输入数据格式：
- 输入的第一行包含一个整数t（1≤t≤3×10^4）——测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含两个整数n和k（1≤n≤3×10^5；1≤k≤2×10^9）；
- 第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）；
- 第三行包含n个整数x_1, x_2, …, x_n（-n≤x_1
输出数据格式：
- 对于每个测试用例，如果你可以在怪物到达你的角色之前杀死所有n个怪物，则输出YES，否则输出NO。

注意：答案中的每个字母可以是任何大小写形式。例如，yEs、yes、Yes和YES都将被视为肯定回答。

示例：
```
Input
5
3 2
1 2 3
-1 2 3
2 1
1 1
-1 1
4 10
3 4 2 5
-3 -2 1 3
5 3
2 1 3 2 5
-3 -2 3 4 5
2 1
1 2
1 2
Output
YES
NO
YES
YES
NO
```

在第一个例子中，你可以按照以下步骤操作：
- 第1秒，向第1个怪物发射1颗子弹，向第3个怪物发射1颗子弹。然后第1个怪物死亡，第2个和第3个怪物向你靠近；
- 第2秒，向第2个怪物发射2颗子弹。然后第2个怪物死亡，第3个怪物向你靠近；
- 第3秒，向第3个怪物发射2颗子弹。然后第3个怪物死亡。

在第二个例子中，你只能发射1颗子弹，所以你在第1秒只能杀死两个怪物中的一个。然后，剩下的怪物靠近并杀死你的角色。题目大意：你正在玩一个电脑游戏，当前的游戏关卡可以看作一条直线，你的角色位于这条直线的点0处。有n个怪物试图杀死你的角色；第i个怪物有a_i的生命值，最初位于点x_i。 每秒钟发生以下事情： 1. 首先，你向怪物发射最多k颗子弹。每颗子弹瞄准一个怪物，并减少其1点生命值。你可以任意选择每颗子弹的目标（例如，你可以把所有子弹都射向一个怪物，射向不同的怪物，或者选择其他任何组合）。无论怪物的位置和其他任何因素，任何怪物都可以成为子弹的目标； 2. 然后，所有生命值为0或更少的怪物死亡； 3. 然后，所有存活的怪物向你的方向移动1个点（你左边的怪物增加其坐标，你右边的怪物减少其坐标）。如果任何怪物到达你的角色（移动到点0），你将失败。 输入数据格式： - 输入的第一行包含一个整数t（1≤t≤3×10^4）——测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个整数n和k（1≤n≤3×10^5；1≤k≤2×10^9）； - 第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）； - 第三行包含n个整数x_1, x_2, …, x_n（-n≤x_1