CF1814D.Balancing Weapons

You've got a job in a game studio that developed an online shooter, and your first big task is to help to balance weapons. The game has $n$ weapons: the $i$-th gun has an integer fire rate $f_i$ and an integer damage per bullet $d_i$. The $i$-th gun's total firepower is equal to $p_i = f_i \cdot d_i$.

You have to modify the values $d_i$ of some guns in such a way that the new values $d_i$ will still be integers, and the firepower of all guns will become balanced. Given an integer $k$, the guns are said to be balanced if $\max\limits_{1 \le i \le n}{p_i} - \min\limits_{1 \le i \le n}{p_i} \le k$.

Since gamers that play your game don't like big changes, you need to change the values $d_i$ for the minimum possible number of guns. What is the minimum number of guns for which you have to change these values to make the guns balanced?

Note that the new values $d_i$ must be integers greater than $0$.

你进入了一家开发在线射击游戏的工作室工作，你的首个重要任务是协助平衡武器。游戏中共有 $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$ 值？

注意：修改后的 $d_i$ 必须为严格大于 $0$ 的整数。

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

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 3000$; $0 \le k \le 1500$) — the number of guns to balance, and the maximum allowed gap between the most and the least powerful weapons.

The second line contains $n$ integers $f_1, f_2, \dots, f_n$ ($1 \le f_i \le 2000$), where $f_i$ is the fire rate of the $i$-th gun.

The third line contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$), where $d_i$ is the damage per bullet of the $i$-th gun.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $3000$.

第一行包含一个整数 $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$。

For each test case, print the minimum number of guns which damage $d_i$ you have to change in order to make the guns balanced.

Note that the new values $d_i$ must be integers greater than $0$.

对于每个测试用例，输出为使枪支达到平衡所需更改的、造成伤害值 $d_i$ 的枪支的最小数量。

注意：新的 $d_i$ 值必须是大于 $0$ 的整数。

In the first test case, you can set $d_1 = 2$ and $d_2 = 4$. You'll get an array $d = [2, 4, 1, 2]$, and the values of firepower will be $p = [12, 12, 13, 14]$. The guns are balanced, since $14 - 12 \le 2$.

In the second test case, you have to change the value $d_i$ for all three guns. For example, you can set $d = [5151, 5100, 5050]$.

In the third test case, all guns are already balanced, so you don't have to change anything.

在第一个测试用例中，你可以设置 $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]$。

在第三个测试用例中，所有枪支已经处于平衡状态，因此无需进行任何修改。