你在一家开发在线射击游戏的游戏工作室找到了一份工作,你的首要任务是帮助平衡武器。游戏有 $$$n$$$ 武器:第 $$$i$$$ 枪具有整数射速 $$$f_i$$$ 和每颗子弹的整数伤害 $$$d_i$$$。第 $$$i$$$ 炮的总火力等于 $$$p_i = f_i \cdot d_i$$$。
你必须修改一些枪的值$$$d_i$$$,使新值$$$d_i$$$仍然是整数,并且所有枪的火力将变得平衡。给定一个整数 $$$k$$$,如果 $$$\max\limits_{1 \le i \le n}{p_i} - \min\limits_{1 \le i \le n}{p_i} \le k$$$,则称枪是平衡的。
由于玩您游戏的玩家不喜欢大的变化,因此您需要更改值 $$$d_i$$$ 以获得尽可能少的枪支数量。您必须更改这些值才能使枪支平衡的最少枪支数量是多少?
请注意,新值 $$$d_i$$$ 必须是大于 $$$0$$$ 的整数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3000$$$; $$$0 \le k \le 1500$$$) - 要平衡的枪支数量,以及最强和最弱武器之间允许的最大差距。
第二行包含 $$$n$$$ 整数 $$$f_1, f_2, \dots, f_n$$$ ($$$1 \le f_i \le 2000$$$),其中 $$$f_i$$$ 是第 $$$i$$$ 枪的射速。
第三行包含 $$$n$$$ 整数 $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^9$$$),其中 $$$d_i$$$ 是第 $$$i$$$ 枪的每颗子弹的伤害。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。
输出
对于每个测试用例,打印损坏 $$$d_i$$$ 的枪支的最小数量,您必须更改以使枪支平衡。
请注意,新值 $$$d_i$$$ 必须是大于 $$$0$$$ 的整数。
示例
输入 #1
5 4 2 6 3 13 7 1 2 1 2 3 2 100 101 102 100 99 98 5 0 1 12 4 4 3 12 1 3 3 4 2 50 1000 10 1000000000 1 3 5 1 19 11 49 4 72
输出 #1
2 3 0 1 2
注意
在第一个测试用例中,您可以设置 $$$d_1 = 2$$$ 和 $$$d_2 = 4$$$。您将得到一个数组 $$$d = [2, 4, 1, 2]$$$,火力值将为 $$$p = [12, 12, 13, 14]$$$。枪支是平衡的,因为 $$$14 - 12 \le 2$$$。
在第二个测试用例中,您必须更改所有三支枪的值 $$$d_i$$$。例如,您可以设置 $$$d = [5151, 5100, 5050]$$$。
在第三个测试用例中,所有枪支都已平衡,因此您无需进行任何更改。