eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Cakey McCakeFace

Cakey McCakeFace

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Фирменное тесто Cakey McCakeFace, Unknowable Cake, выпекается ежедневно в парижском цехе. Трюк "сделай или сломай" для этого торта - это время приготовления, которое держится в секрете. Ева, известный шпион, хочет украсть этот секрет, и Ваша задача - помочь ей.

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

Ева тайно установила детекторы в передней и задней части духовки. Они записывают сигнал каждый раз, когда торт проходит через двери. Таким образом, торт будет запускать детектор входа через некоторое время t, когда он проходит через переднюю дверь, а затем активировать детектор выхода в момент времени точно t + cooking_time, когда он проходит через заднюю дверь. дверь (все торты в Cakey McCakeFace всегда отлично приготовлены).

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

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

Первая строка содержит число n (1n2000) раз срабатывания детектора входа. Вторая строка содержит число m (1m2000) раз срабатывания детектора выхода. Третья строка содержит n целочисленных временных меток, при которых сработал детектор входа, отсортированных по возрастанию без повторений. Четвертая строка содержит m целочисленных временных меток, при которых был активирован выходной детектор, отсортированных в порядке возрастания без повторений. Временные метки принимают значения от 0 до 10^9.

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

Выведите единственное целое число - Ваше лучшее предположение о секретном времени cooking_time (положительная или нулевая) разница во времени, которая максимизирует количество соответствий времени входа и выхода. Если существует несколько таких значений, то вывести наименьшее.

Пример

Входные данные #1
5
5
0 10 12 20 30
1 5 17 27 50
Выходные данные #1
5
Источник 2017 ACM Southwestern Europe Regional Contest (SWERC), Париж, Ноябрь 26, Задача A