Description

有 2K 个数构成的正整数序列（K 也必为正整数），要把这 2K 个 数组合成 K 对，就会形成 K 个和。求一种组合方式，使得这 K 个和中的最大值最小，输出这个最小的最大值即可。

Format

Input

第一行一个正整数 K，以下 K 行，每行 2 个正整数 x 和 y，代 表该序列中含有 x 个 y。

Output

最小的最大值.

Sample 1

Input

3
1 8
2 5
1 2

Output

10

Limitation

对于 100%的数据，K<=100000 x,y<=1000000000

Source

比赛用题库