Вы играете в игру, похожую на Сокобан, на бесконечной числовой прямой. Игра дискретна, поэтому вы рассматриваете только целочисленные позиции на прямой.
Вы начинаете в позиции \(0\). Есть \(n\) коробок, \(i\)-я коробка находится на позиции \(a_i\). Все позиции коробок различны. Также есть \(m\) специальных позиций, \(j\)-я позиция — это \(b_j\). Все специальные позиции также различны.
За один ход можно пройти на одну позицию влево или вправо. Если в направлении вашего движения стоит коробка, то вы толкаете коробку на следующую позицию в этом направлении. Если следующая позиция занята другой коробкой, то эта коробка также двигается на следующую позицию, и так далее. Нельзя ходить сквозь коробки. Нельзя тащить коробки на себя.
Разрешается совершить произвольное количество ходов (возможно, ноль). Ваша цель — поместить как можно больше коробок на специальные позиции. Обратите внимание, что некоторые коробки могут уже находиться на специальных позициях.
Выходные данные
На каждый набор входных данных выведите одно целое число — максимальное количество коробок, которые можно поставить на специальные позиции.
Примечание
В первом наборе входных данных можно пойти на \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|