C - Max Ai+Bj Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250 点

問題文

長さ N の整数列 A,B が与えられます。1 以上 N 以下の整数 i,j を選んで、 A_i + B_j の値を最大化してください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9\,(i=1,2,\dots,N)
  • |B_j| \leq 10^9\,(j=1,2,\dots,N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

A_i + B_j の最大値を出力せよ。

入力例 1

2
-1 5
3 -7

出力例 1

8

(i,j)=(1,1),(1,2),(2,1),(2,2) に対する A_i+B_j の値はそれぞれ 2,-8,8,-2 であり、(i,j)=(2,1) が最大値 8 を達成します。

入力例 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

出力例 2

33

Score : 250 points

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9 (i=1,2,\dots,N)
  • |B_j| \leq 10^9 (j=1,2,\dots,N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the maximum possible value of A_i + B_j.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33