Березовая аллея

На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной W метров. Вдоль левой стороны аллеи растет N берез, а вдоль правой — M берез, при этом i-я береза с левой стороны аллеи находится на расстоянии a_i метров от начала аллеи, а j-я береза с правой стороны — на расстоянии b_j метров от начала аллеи.

Отдыхая в деревне прошедшим летом, один юный информатик обнаружил, что кору берез стали грызть зайцы. Чтобы защитить деревья от зайцев, мальчик решил окружить березы красной лентой (зайцы не любят красный цвет и не станут заходить на огражденную лентой территорию). К сожалению, в его распоряжении оказалась только лента длиной L метров, которую, к тому же, нельзя было разрезать. Единственное, что можно было делать в этом случае — окружить этой лентой как можно больше берез. При этом, чтобы сохранить аллею, необходимо окружить на каждой стороне аллеи хотя бы одну березу.

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

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

Первая строка входного файла INPUT.TXT содержит два разделенных пробелом целых числа: длину ленты L и ширину аллеи W (1 ≤ L ≤ 2×10⁵, 1 ≤ W ≤ 10⁴).

Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число N — количество берез (1 ≤ N ≤ 2000), а третья строка содержит N различных целых чисел a₁, a₂, …, a_N, заданных по возрастанию (0 ≤ a_i ≤ 10⁵).

Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число M — количество берез (1 ≤ M ≤ 2000), а пятая строка содержит M различных целых чисел b₁, b₂, …, b_M, заданных по возрастанию (0 ≤ b_i ≤ 10⁵).

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

Выходной файл OUTPUT.TXT должен содержать одно целое число: максимальное количество берез, которое можно оградить заданной лентой. Гарантируется, что если максимальное число берез, которое можно оградить лентой длины L, равно X, то нет способа оградить (X + 1) березу лентой длины (L + 10^-5).

Примеры

Пояснения к примерам

В первом примере можно, например, оградить березы способом, указанным на рисунке ниже.

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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]