Cakey McCakeFace
Фирменное тесто Cakey McCakeFace, Unknowable Cake, выпекается ежедневно в парижском цехе. Трюк "сделай или сломай" для этого торта - это время приготовления, которое держится в секрете. Ева, известный шпион, хочет украсть этот секрет, и Ваша задача - помочь ей.
Торты готовятся в одной огромной духовке, которая имеет ровно одну переднюю и одну заднюю дверь. Сырые пирожные вставляются через переднюю дверь. После того, как точное и очень секретное время приготовления прошло, торты выходят из духовки через заднюю дверь. Только один торт может пройти через переднюю или заднюю дверь в любой момент времени.
Ева тайно установила детекторы в передней и задней части духовки. Они записывают сигнал каждый раз, когда торт проходит через двери. Таким образом, торт будет запускать детектор входа через некоторое время t, когда он проходит через переднюю дверь, а затем активировать детектор выхода в момент времени точно t + cooking_time, когда он проходит через заднюю дверь. дверь (все торты в Cakey McCakeFace всегда отлично приготовлены).
Через несколько дней она получает два набора меток времени (в милисекундах), соответствующих детекторам входа и выхода. К сожалению, детекторы неисправны: они иногда срабатывают, когда пирог не прошел, или могут не срабатывать при прохождении пирога. Ева заметила, что она может догадаться о значении секретного времени cooking_time, найдя разницу во времени, которая максимизирует количество соответствий времени входа и выхода. Помогите Еве его вычислить.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 2000) раз срабатывания детектора входа. Вторая строка содержит число m (1 ≤ m ≤ 2000) раз срабатывания детектора выхода. Третья строка содержит n целочисленных временных меток, при которых сработал детектор входа, отсортированных по возрастанию без повторений. Четвертая строка содержит m целочисленных временных меток, при которых был активирован выходной детектор, отсортированных в порядке возрастания без повторений. Временные метки принимают значения от 0 до 10^9.
Выходные данные
Выведите единственное целое число - Ваше лучшее предположение о секретном времени cooking_time (положительная или нулевая) разница во времени, которая максимизирует количество соответствий времени входа и выхода. Если существует несколько таких значений, то вывести наименьшее.