Вам даны два массива целых чисел \(a_1,a_2,\dots,a_n\) и \(b_1,b_2,\dots,b_m\).
Алиса и Боб играют в игру. Алиса ходит первой, а затем они ходят по очереди.
Они играют на доске \(n \times m\) (\(n\) строк и \(m\) столбцов). Изначально в клетке в первой строке и первом столбце стоит ладья.
В свой ход игрок может сделать одну из следующих двух операций:
- Переместить ладью в другую клетку в том же ряду или в том же столбце с текущей клеткой. Игрок не может переместить ладью в клетку, которая уже была посещена \(1000\) раз до этого (т. е. ладья может находиться на одной клетке не более \(1000\) раз за всю игру). Обратите внимание, что стартовая клетка считается уже посещенной один раз в начале игры.
- Немедленно закончить игру со счетом \(a_r+b_c\), где \((r, c)\) — координаты текущей клетки (т. е. ладья находится в \(r\)-й строку \(c\)-м столбце).
Боб хочет максимизировать счет игры, а Алиса хочет минимизировать его. Если они оба играют оптимально, каким будет итоговый счет?
Выходные данные
Выведите одну строку — итоговый счет игры.
Примечание
В первом примере Алиса передвинет ладью на клетку \((2, 1)\), а Боб передвинет ладью обратно на клетку \((1, 1)\). Этот процесс повторится \(999\) раз, а затем, после хода Алисы, Боб не сможет передвинуть ладью обратно на клетку \((1, 1)\), так как она уже была посещена \(1000\) раз. Поэтому счет игры будет равен \(a_2+b_1=4\).
Во втором примере счет игры равен \(a_3+b_5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
3 2
2
|
4
|
|
2
|
4 5
235499701 451218171 355604420 132973458
365049318 264083156 491406845 62875547 175951751
|
531556171
|