您正在玩电脑游戏。该游戏的当前等级可以建模为一条直线。您的角色位于该行的 $$$0$$$ 点。有 $$$n$$$ 怪物试图杀死你的角色;第 $$$i$$$ 个怪物的生命值等于 $$$a_i$$$,并且最初位于 $$$x_i$$$ 点。
每秒都会发生以下情况:
- 首先,你向怪物发射最多 $$$k$$$ 子弹。每颗子弹只瞄准一个怪物,并使其生命值降低 $$$1$$$。对于每颗子弹,您可以任意选择其目标(例如,您可以向一个怪物发射所有子弹,向不同的怪物发射所有子弹,或选择任何其他组合)。任何怪物都可以成为子弹的目标,无论其位置和任何其他因素如何;
- 然后,所有生命值为 $$$0$$$ 或更少的活着的怪物都会死亡;
- 然后,所有活着的怪物都会向你移动$$$1$$$点(你左边的怪物将坐标增加$$$1$$$,你右边的怪物将坐标减少$$$1$$$)。如果任何怪物到达你的角色(移动到$$$0$$$点),你就输了。
你能生存并杀死所有 $$$n$$$ 怪物而不让它们到达你的角色吗?
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — 测试用例的数量。
每个测试用例由三行组成:
- 第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 2 \cdot 10^9$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);
- 第三行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$-n \le x_1 < x_2 < x_3 < \dots < x_n \le n$$$; $$$x_i \ne 0$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,如果您可以在 $$$n$$$ 怪物到达您的角色之前杀死它们,则打印 YES,否则打印 NO。
您可以以任何大小写(大写或小写)输出答案的每个字母。例如,字符串 yEs、yes、Yes 和 YES 都将被识别为肯定响应。
示例
输入 #1
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
输出 #1
YES NO YES YES NO
注意
在第一个示例中,您可以执行以下操作:
- 在第 $$$1$$$-st 秒内,向 $$$1$$$-st 怪物发射 $$$1$$$ 子弹,并向 $$$3$$$-rd 怪物发射 $$$1$$$ 子弹。然后$$$1$$$-st 怪物死亡,$$$2$$$-nd 和$$$3$$$-rd 怪物靠近;
- 在第 $$$2$$$-nd 秒内,向第 $$$2$$$-nd 怪物发射 $$$2$$$ 子弹。然后第 $$$2$$$-rd 怪物死亡,$$$3$$$-rd 怪物靠近;
- 在第 $$$3$$$-rd 秒内,向 $$$3$$$-rd 怪物发射 $$$2$$$ 子弹。然后$$$3$$$-rd 怪物就死了。
在第二个例子中,你只能发射 $$$1$$$ 子弹,因此你只能在 $$$1$$$-st 秒内杀死两个怪物之一。然后,剩下的怪物靠近并杀死你的角色。