B - 工作分配

得分：$200$ 分

问题描述

你的公司有 $N$ 名员工，编号为 Employee $1$ 至 $N$。
你收到了两个工作指令，称为工作 A 和 B，它们必须完成。
员工 $i$ 可以在 $A_i$ 分钟内完成工作 A，并在 $B_i$ 分钟内完成工作 B。

你需要为每个工作指派一个员工。
你可以将两个工作指派给同一个员工，这样他/她完成它们所需的时间是他/她分别完成它们所需时间的总和。
如果你将工作指派给不同的员工，那么完成工作所需时间是他们各自完成工作所需时间的较长者。
找出完成工作所需的最短时间。

约束条件

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

输入

从标准输入中以以下格式提供输入：

$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$，他们将分别在 $4$ 分钟和 $5$ 分钟内完成它们。
由于将工作指派给了不同的员工，完成这两个工作将需要 $\max(4, 5) = 5$ 分钟。
不能更早地完成工作。

3
11 7
3 2
6 7

5

最优解是将两个工作都分配给员工 $2$。
请注意，如果将两个工作指派给同一位员工，他/她完成它们所需的时间是他/她分别完成它们所需时间的总和。