最佳组队(bestteam)-T6

题目描述

班里有 $N$ 名学生，每名学生有两个能力值：编程 $P\_i$ 和数学 $M\_i$。 现在要选出 2 名学生 $i、j$ 组成团队。团队战斗力定义为：$\min(P\_i + P\_j,\ M\_i + M\_j)$。 现要求“团队战斗力”的最大值。

输入格式

第一行 1 个整数 $N$（$1 \leq N \leq 100000$）。 下面 $N$ 行，每行 2 个整数 $P\_i,\ M\_i$（$0 \leq P\_i,\ M\_i \leq 1000000$）。

数据范围

• 对于 50% 的数据，$1 \leq N \leq 10000$
• 对于 100% 的数据，$1 \leq N \leq 100000$

输出格式

输出一个整数。

样例

输入

6
9 2
1 5
9 6
9 9
3 8
1 0

输出

15