← 返回题目列表

Codeforces · 1814/D

D. 平衡武器

中文机器翻译题面 查看原题

你在一家开发在线射击游戏的游戏工作室找到了一份工作,你的首要任务是帮助平衡武器。游戏有 $$$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]$$$。

在第三个测试用例中,所有枪支都已平衡,因此您无需进行任何更改。