C. Частное и остаток
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы два массива целых чисел $$$q_1, q_2, \dots, q_n$$$ и $$$r_1, r_2, \dots, r_n$$$, а также целое число $$$k$$$. Вы можете проводить следующую операцию любое количество раз (в том числе и ноль):

  1. Выбрать два целых числа $$$x$$$ и $$$y$$$ такие, что
    • $$$1 \le y \lt x \le k$$$;
    • существует индекс $$$i$$$ такой, что $$$q_i = \left\lfloor \frac{x}{y} \right\rfloor$$$ (округленное вниз);
    • существует индекс $$$j$$$ такой, что $$$r_j = x \bmod y$$$.
  2. Удалить $$$q_i$$$ из массива $$$q$$$ и $$$r_j$$$ из массива $$$r$$$. Если есть несколько вхождений $$$q_i$$$ в $$$q$$$, удаляется только одно из них; аналогично с $$$r_j$$$ и массивом $$$r$$$.

Определите максимальное количество операций, которое вы можете применить к заданным массивам $$$r$$$ и $$$q$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 10^{18}$$$) — размер массивов $$$q$$$ и $$$r$$$ и верхнее ограничение на $$$x$$$ и $$$y$$$.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$q_1, q_2, \dots, q_n$$$ ($$$1 \le q_i \le 10^9$$$) — массив $$$q$$$.

В третьей строке заданы $$$n$$$ целых чисел $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^9$$$) — массив $$$r$$$.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество операций, которое вы можете применить к заданным массивам.

Пример
Входные данные
3
1 100
1
27
3 10
5 6 5
7 1 7
5 42
5 4 2 2 1
9 8 9 8 100
Выходные данные
1
0
3
Примечание

В первом наборе входных данных можно применить одну операцию: можно выбрать $$$x = 69$$$ и $$$y = 42$$$. Тогда $$$\left\lfloor \frac{69}{42} \right\rfloor = 1 = q_1$$$ и $$$69 \bmod 42 = 27 = r_1$$$.

Во втором наборе невозможно применить ни одной операции, так как нельзя подобрать подходящие $$$x$$$ и $$$y$$$.

В третьем наборе можно применить три операции:

  1. $$$x = 42$$$, $$$y = 17$$$: $$$\left\lfloor \frac{42}{17} \right\rfloor = 2 = q_3$$$ и $$$42 \bmod 17 = 8 = r_2$$$;
  2. $$$x = 41$$$, $$$y = 16$$$: $$$\left\lfloor \frac{41}{16} \right\rfloor = 2 = q_4$$$ и $$$41 \bmod 16 = 9 = r_1$$$;
  3. $$$x = 20$$$, $$$y = 12$$$: $$$\left\lfloor \frac{20}{12} \right\rfloor = 1 = q_5$$$ и $$$20 \bmod 12 = 8 = r_4$$$;
После применения данных операций у вас останутся массивы $$$q = [5, 4]$$$ и $$$r = [9, 100]$$$, к которым больше невозможно применить ни одной операции.