#JXD2004. 强哥的友情之战

强哥的友情之战

强哥和大雄正在玩一个有趣的游戏。他们手里分别拿着一串数字,强哥的数字叫 ​勇者之剑​(序列 AA),大雄的数字叫 ​守护之盾​(序列 BB)。他们想找出 ​最强攻击力​,方法是:

在强哥的勇者之剑中挑一个数字 AiA_i,并从大雄的守护之盾中挑一个数字 BjB_j,让两人组合的攻击力 Ai+BjA_i + B_j 达到最大值!

他们请你帮忙计算出这个最强攻击力。

数据范围

  • 强哥和大雄每人都有 NN 个数字,1N500,0001 \leq N \leq 500,000
  • 强哥勇者之剑的每个数字 Ai109|A_i| \leq 10^9
  • 大雄守护之盾的每个数字 Bj109|B_j| \leq 10^9

输入格式

输入通过标准输入,格式如下:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
  • 第一行:数字个数 NN
  • 第二行:强哥勇者之剑的数字序列 AA
  • 第三行:大雄守护之盾的数字序列 BB

输出格式

输出一个整数,表示最强攻击力 Ai+BjA_i + B_j 的最大值。


样例输入1

2
-1 5
3 -7

样例输出1

8

解释​:

  • 强哥选择 A2=5A_2=5,大雄选择 B1=3B_1=3,他们的攻击力为 A2+B1=8A_2 + B_1 = 8,达到最大值。

友情提示​:

  • 策略提示​:找到勇者之剑的最大值 AmaxA_{\text{max}} 和守护之盾的最大值 BmaxB_{\text{max}},然后将它们相加即可得到答案。