E. Два массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива целых чисел $$$a_1,a_2,\dots,a_n$$$ и $$$b_1,b_2,\dots,b_m$$$.

Алиса и Боб играют в игру. Алиса ходит первой, а затем они ходят по очереди.

Они играют на доске $$$n \times m$$$ ($$$n$$$ строк и $$$m$$$ столбцов). Изначально в клетке в первой строке и первом столбце стоит ладья.

В свой ход игрок может сделать одну из следующих двух операций:

  1. Переместить ладью в другую клетку в том же ряду или в том же столбце с текущей клеткой. Игрок не может переместить ладью в клетку, которая уже была посещена $$$1000$$$ раз до этого (т. е. ладья может находиться на одной клетке не более $$$1000$$$ раз за всю игру). Обратите внимание, что стартовая клетка считается уже посещенной один раз в начале игры.
  2. Немедленно закончить игру со счетом $$$a_r+b_c$$$, где $$$(r, c)$$$ — координаты текущей клетки (т. е. ладья находится в $$$r$$$-й строку $$$c$$$-м столбце).

Боб хочет максимизировать счет игры, а Алиса хочет минимизировать его. Если они оба играют оптимально, каким будет итоговый счет?

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$) — длины массивов $$$a$$$ и $$$b$$$ (которые совпадают с размерами доски).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^8$$$).

Третья строка содержит $$$m$$$ целых чисел $$$b_1, b_2,\dots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^8$$$).

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

Выведите одну строку — итоговый счет игры.

Примеры
Входные данные
2 1
3 2
2
Выходные данные
4
Входные данные
4 5
235499701 451218171 355604420 132973458
365049318 264083156 491406845 62875547 175951751
Выходные данные
531556171
Примечание

В первом примере Алиса передвинет ладью на клетку $$$(2, 1)$$$, а Боб передвинет ладью обратно на клетку $$$(1, 1)$$$. Этот процесс повторится $$$999$$$ раз, а затем, после хода Алисы, Боб не сможет передвинуть ладью обратно на клетку $$$(1, 1)$$$, так как она уже была посещена $$$1000$$$ раз. Поэтому счет игры будет равен $$$a_2+b_1=4$$$.

Во втором примере счет игры равен $$$a_3+b_5$$$.