C. 1D Сокобан
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в игру, похожую на Сокобан, на бесконечной числовой прямой. Игра дискретна, поэтому вы рассматриваете только целочисленные позиции на прямой.

Вы начинаете в позиции $$$0$$$. Есть $$$n$$$ коробок, $$$i$$$-я коробка находится на позиции $$$a_i$$$. Все позиции коробок различны. Также есть $$$m$$$ специальных позиций, $$$j$$$-я позиция — это $$$b_j$$$. Все специальные позиции также различны.

За один ход можно пройти на одну позицию влево или вправо. Если в направлении вашего движения стоит коробка, то вы толкаете коробку на следующую позицию в этом направлении. Если следующая позиция занята другой коробкой, то эта коробка также двигается на следующую позицию, и так далее. Нельзя ходить сквозь коробки. Нельзя тащить коробки на себя.

Разрешается совершить произвольное количество ходов (возможно, ноль). Ваша цель — поместить как можно больше коробок на специальные позиции. Обратите внимание, что некоторые коробки могут уже находиться на специальных позициях.

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

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

Затем следует описание $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — количество коробок и количество специальных позиций, соответственно.

Во второй строке каждого набора входных данных записаны $$$n$$$ различных целых чисел в возрастающем порядке $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_1 < a_2 < \dots < a_n \le 10^9$$$; $$$a_i \neq 0$$$) — начальные позиции коробок.

В третьей строке каждого набора входных данных записаны $$$m$$$ различных целых чисел в возрастающем порядке $$$b_1, b_2, \dots, b_m$$$ ($$$-10^9 \le b_1 < b_2 < \dots < b_m \le 10^9$$$; $$$b_i \neq 0$$$) — специальные позиции.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
5 6
-1 1 5 11 15
-4 -3 -2 6 7 15
2 2
-1 1
-1000000000 1000000000
2 2
-1000000000 1000000000
-1 1
3 5
-1 1 2
-2 -1 1 2 5
2 1
1 2
10
Выходные данные
4
2
0
3
1
Примечание

В первом наборе входных данных можно пойти на $$$5$$$ направо: коробка на позиции $$$1$$$ окажется на позиции $$$6$$$, а коробка на позиции $$$5$$$ — на позиции $$$7$$$. Затем можно пойти на $$$6$$$ налево и встать в позицию $$$-1$$$, сдвинув коробку в $$$-2$$$. В конце коробки стоят на позициях $$$[-2, 6, 7, 11, 15]$$$, соответственно. Среди них позиции $$$[-2, 6, 7, 15]$$$ специальные, поэтому ответ равен $$$4$$$.

Во втором наборе входных данных можно дотолкать коробку из $$$-1$$$ в $$$-10^9$$$, а затем коробку из $$$1$$$ в $$$10^9$$$, и получить ответ $$$2$$$.

Третий набор входных данных показывает, что не разрешается тащить коробки на себя, поэтому нельзя их притащить на специальные позиции.

В четвертом наборе входных данных все коробки уже находятся на специальных позициях, поэтому можно ничего не делать и все равно получить ответ $$$3$$$.

В пятом наборе входных данных особенных позиций меньше, чем коробок. Можно пойти на $$$8$$$ или на $$$9$$$ направо, чтобы какая-нибудь коробка встала в $$$10$$$.