D. Балансировка пушек
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы получили работу в игровой студии, которая разработала и поддерживает онлайн шутер, и ваша первая по-настоящему большая работа — это помочь в балансировке оружия. В игре есть $$$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$$$.

Пример
Входные данные
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
Выходные данные
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]$$$.

В третьем наборе все оружие уже сбалансировано, и вам не нужно ничего менять.