C. Премьера
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Так бывает, что два очень ожидаемых блокбастера выходят в один и тот же день. Вот и в этот раз в кинотеатрах одновременно начинают показывать два легендарных, но очень разных фильма: «Борби» и «Опергеймер». У Руслана выдался редкий выходной как раз в день этой премьеры.

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

Так как выходных у Руслана бывает очень мало, а его время ценно, он специально купил билеты так, чтобы между началом первого по времени сеанса и концом второго прошло как можно меньше времени. Вычислите это минимальное время.

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

В первой строке ввода даны два целых положительных числа $$$t_b$$$ и $$$t_o$$$ — длительности фильмов «Борби» и «Опергеймер», соответственно, причём $$$t_b, t_o \le 10^9$$$.

Во второй строке дано целое положительное число $$$n$$$ — число сеансов фильма «Борби» в кинотеатре.

В следующей строке дано $$$n$$$ целых неотрицательных чисел $$$b_i$$$ — времена начала сеансов фильма «Борби» в порядке возрастания, $$$b_i \le 10^9$$$.

В следующей строке дано целое положительное число $$$m$$$ — число сеансов фильма «Опергеймер».

В следующей строке дано $$$n$$$ целых неотрицательных чисел $$$o_j$$$ — времена начала сеансов фильма «Опергеймер» в порядке возрастания, $$$o_j \le 10^9$$$.

Сеансы одного и того же фильма в расписании могут пересекаться.

Гарантируется, что существует два непересекающихся сеанса двух разных фильмов.

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

Выведите единственное число — ответ на задачу.

Система оценки
Группа тестовДополнительные ограниченияБаллыНеобходимые группы
$$$n$$$$$$m$$$
$$$1$$$    $$$n = 1$$$    $$$m \le 2 \cdot 10^5$$$$$$35$$$—
$$$2$$$    $$$n \le 10^3$$$    $$$m \le 10^3$$$$$$35$$$—
$$$3$$$    $$$n \le 2 \cdot 10^5$$$    $$$m \le 2 \cdot 10^5$$$$$$30$$$$$$1, 2$$$

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

Примеры
Входные данные
100 180
3
0 200 340
3
20 150 320
Выходные данные
290
Входные данные
100 180
1
700
6
0 200 400 600 800 1000
Выходные данные
400
Примечание

В первом примере из условия варианты пар непересекающихся сеансов следующие:

  1. «Борби» во время $$$0$$$, который продлится до времени $$$100$$$, и потом «Опергеймер» во время $$$150$$$, который продлится до времени $$$330$$$, в сумме выйдет время $$$330 - 0 = 330$$$
  2. «Борби» во время $$$0$$$, который продлится до времени $$$100$$$, и потом «Опергеймер» во время $$$320$$$, который продлится до времени $$$500$$$, в сумме выйдет время $$$500 - 0 = 500$$$
  3. «Борби» во время $$$200$$$, который продлится до времени $$$300$$$, и потом «Опергеймер» во время $$$320$$$, который продлится до времени $$$500$$$, в сумме выйдет время $$$500 - 200 = 300$$$
  4. «Опергеймер» во время $$$20$$$, который продлится до времени $$$200$$$, и потом «Борби» во время $$$340$$$, который продлится до времени $$$440$$$, в сумме выйдет время $$$440 - 20 = 420$$$
  5. «Опергеймер» во время $$$150$$$, который продлится до времени $$$330$$$, и потом «Борби» во время $$$340$$$, который продлится до времени $$$440$$$, в сумме выйдет время $$$440 - 150 = 290$$$

Меньше всего времени ($$$290$$$) уйдёт на последнюю пару сеансов в списке.

Во втором примере сеанс фильма «Борби» всего один, и варианты непересакающихся сеансов следующие:

  1. «Опергеймер» во время $$$0$$$, который продлится до времени $$$180$$$, и потом «Борби» во время $$$700$$$, который продлится до времени $$$800$$$, в сумме выйдет время $$$800 - 0 = 800$$$
  2. «Опергеймер» во время $$$200$$$, который продлится до времени $$$380$$$, и потом «Борби» во время 700, который продлится до времени $$$800$$$, в сумме выйдет время $$$800 - 200 = 600$$$
  3. «Опергеймер» во время $$$400$$$, который продлится до времени $$$580$$$, и потом «Борби» во время $$$700$$$, который продлится до времени $$$800$$$, в сумме выйдет время $$$800 - 400 = 400$$$
  4. «Борби» во время $$$700$$$, который продлится до времени 800, и потом «Опергеймер» во время $$$1000$$$, который продлится до времени $$$1180$$$, в сумме выйдет время $$$1180 - 700 = 480$$$

Меньше всего времени ($$$400$$$) уйдёт на пару сеансов номер $$$3$$$ в списке.