任务分配

题目描述

你的公司有从员工 $1$ 到员工 $N$ 的 $N$ 名员工。

现在你接到了工作 A 和工作 B 两件工作,必须将它们完成。

员工 $i$ 可以用 $A_i$ 分钟完成工作 A,用 $B_i$ 分钟完成工作 B。

你为工作 A 和工作 B 各分配 $1$ 名员工。

将同一名员工分配给两件工作也可以,但此时完成两件工作所需的时间是分别完成两件工作所需时间之和。

如果将工作 A 和工作 B 分配给不同的员工,则完成两件工作所需的时间是各工作所需时间中较长的一个。

求完成两件工作所需时间的最小可能值。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$A_3$ $B_3$
$\hspace{15pt} \vdots$
$A_N$ $B_N$

输出格式

输出完成两件工作所需时间的最小可能值 [分钟]。

样例

3
8 5
4 4
7 9

5

将工作 A 分配给员工 $2$,工作 B 分配给员工 $1$,则工作 A, B 分别在 $4, 5$ 分钟内完成。

由于两件工作分配给了不同的员工,完成两件工作所需的时间是 $\max(4, 5) = 5$ [分钟]。

两件工作不会在比这更短的时间内完成。

3
11 7
3 2
6 7

5

将两件工作都分配给员工 $2$ 是最优的。

注意将同一名员工分配给两件工作时,完成两件工作所需的时间是分别完成所需时间之和。

数据范围

• $2 \le N \le 1000$
• $1 \le A_i \le 10^5$
• $1 \le B_i \le 10^5$
• 输入中包含的值均为整数