给定两个整数数组 $$$a_1,a_2,\dots,a_n$$$ 和 $$$b_1,b_2,\dots,b_m$$$。
Alice 和 Bob 要去玩一个游戏。爱丽丝先行动,他们轮流行动。
他们在大小为 $$$n \times m$$$ 的网格上进行游戏(具有 $$$n$$$ 行和 $$$m$$$ 列的网格)。最初,有一个车位于网格的第一行第一列。
在她/他的移动过程中,玩家可以执行以下两种操作之一:
1. 将车移动到当前单元格同一行或同一列的不同单元格。玩家无法将车移动到之前已访问过 $$$1000$$$ 次的单元格(即,在整个游戏期间,车最多可以在某个单元格中停留 $$$1000$$$ 次)。请注意,起始单元被视为在游戏开始时被访问过一次。
2. 立即结束游戏,得分为 $$$a_r+b_c$$$,其中 $$$(r, c)$$$ 是当前单元格(即,车位于第 $$$r$$$ 行和 $$$c$$$ 列)。
Bob 想要最大化分数,而 Alice 想要最小化分数。如果他们都以最佳状态玩这个游戏,那么游戏的最终得分是多少?
输入
第一行包含两个整数 $$$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$$$)。
输出
打印包含游戏最终得分的一行。
示例
输入 #1
2 1 3 2 2
输出 #1
4
输入 #2
4 5 235499701 451218171 355604420 132973458 365049318 264083156 491406845 62875547 175951751
输出 #2
531556171
注意
在第一个测试用例中,Alice 将车移动到 $$$(2, 1)$$$,Bob 将车移动到 $$$(1, 1)$$$。这个过程将重复 $$$999$$$ 次,直到最后,在 Alice 移动车后,Bob 无法将其移回 $$$(1, 1)$$$,因为它之前已被访问过 $$$1000$$$ 次。所以游戏最终得分为$$$a_2+b_1=4$$$。
在第二个测试用例中,游戏的最终得分为$$$a_3+b_5$$$。