Job Assignment

题目描述

你的公司有 $N$ 名员工，称为员工 $1$ 到 $N$.
你收到了两项工作，称为工作 A 和 B，必须完成它们。
员工 $i$ 可以在 $A_i$ 分钟内完成工作 A，$B_i$ 分钟内完成工作 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

3
11 7
3 2
6 7

5

提示

$2 \le N \le 1000$ $1 \le A_i \le 10^5$ $1 \le B_i \le 10^5$ 输入中的所有数值都是整数。如果你把工作 A 分配给员工 $2$，把工作 B 分配给员工 $1$，他们会分别在 $4$ 和 $5$ 分钟内完成它们。
由于你把工作分配给不同的员工，完成两项工作将花费 $\max(4, 5) = 5$ 分钟。
不可能更早完成。
把两项工作都分配给员工 $2$ 是最优的。
注意如果你把两项工作都分配给同一名员工，他/她完成它们所需的时间是他/她单独完成它们所需时间的和。

标签: AtCoder|abc194B

来源

AtCoder|abc194B