CF1710E.Two Arrays

You are given two arrays of integers $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_m$.

Alice and Bob are going to play a game. Alice moves first and they take turns making a move.

They play on a grid of size $n \times m$ (a grid with $n$ rows and $m$ columns). Initially, there is a rook positioned on the first row and first column of the grid.

During her/his move, a player can do one of the following two operations:

1. Move the rook to a different cell on the same row or the same column of the current cell. A player cannot move the rook to a cell that has been visited $1000$ times before (i.e., the rook can stay in a certain cell at most $1000$ times during the entire game). Note that the starting cell is considered to be visited once at the beginning of the game.
2. End the game immediately with a score of $a_r+b_c$, where $(r, c)$ is the current cell (i.e., the rook is on the $r$-th row and $c$-th column).

Bob wants to maximize the score while Alice wants to minimize it. If they both play this game optimally, what is the final score of the game?

给你两个整数数组 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_m$。

爱丽丝（Alice）和鲍勃（Bob）将进行一场游戏。爱丽丝先手，之后两人轮流进行操作。

他们在大小为 $n \times m$ 的网格（即有 $n$ 行、$m$ 列的网格）上进行游戏。初始时，一个车（rook）位于网格的第一行第一列。

在每次操作中，当前玩家可执行以下两种操作之一：

1. 将车移动到与当前格子同行或同列的另一个格子。玩家不能将车移动到已被访问过 $1000$ 次的格子（即在整个游戏中，车在任意特定格子最多停留 $1000$ 次）。注意：初始位置在游戏开始时即被视为已被访问一次。
2. 立即结束游戏，并获得分数 $a_r+b_c$，其中 $(r, c)$ 是当前格子（即车位于第 $r$ 行、第 $c$ 列）。

鲍勃希望最大化最终得分，而爱丽丝希望最小化最终得分。若双方均以最优策略进行游戏，则游戏的最终得分是多少？

The first line contains two integers $n$ and $m$ ($1 \leq n,m \leq 2 \cdot 10^5$) — the length of the arrays $a$ and $b$ (which coincide with the number of rows and columns of the grid).

The second line contains the $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 5 \cdot 10^8$).

The third line contains the $m$ integers $b_1, b_2,\dots, b_n$ ($1 \leq b_i \leq 5 \cdot 10^8$).

第一行包含两个整数 $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_m$（$1 \leq b_i \leq 5 \cdot 10^8$）。

Print a single line containing the final score of the game.

输出一行，包含游戏的最终得分。

In the first test case, Alice moves the rook to $(2, 1)$ and Bob moves the rook to $(1, 1)$. This process will repeat for $999$ times until finally, after Alice moves the rook, Bob cannot move it back to $(1, 1)$ because it has been visited $1000$ times before. So the final score of the game is $a_2+b_1=4$.

In the second test case, the final score of the game is $a_3+b_5$.

在第一个测试用例中，Alice 将车移动到 $(2, 1)$，Bob 将车移动到 $(1, 1)$。该过程将重复 $999$ 次，直到最后，在 Alice 移动车之后，Bob 无法再将其移回 $(1, 1)$，因为该位置此前已被访问过 $1000$ 次。因此，游戏的最终得分为 $a_2+b_1=4$。

在第二个测试用例中，游戏的最终得分为 $a_3+b_5$。