Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 10 сек. Память: 128 Мб Сложность: 70%)

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

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

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

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

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

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

Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число N — количество берез (1 ≤ N ≤ 2000), а третья строка содержит N различных целых чисел a1, a2, …, aN, заданных по возрастанию (0 ≤ ai ≤ 105).

Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число M — количество берез (1 ≤ M ≤ 2000), а пятая строка содержит M различных целых чисел b1, b2, …, bM, заданных по возрастанию (0 ≤ bi ≤ 105).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
118 4
3
0 3 6
4
0 3 6 10
5
25 3
1
0
1
0
0

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

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

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


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Кастинг
 B. Города - 2
 C. A + B = C
 D. Березовая аллея
 E. Игральные кубики
 F. Имена
 G. Две окружности - 2
 H. Столицы

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru