← 返回题目列表

AtCoder · abc194_b

B. 工作分配

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

贵公司有 N 员工,称为 Employee 1 通过 N.
您已收到两个工作订单,称为工作 A 和 B,必须完成。
员工 i 可以完成工作 A A_i 分钟和工作 B B_i 分钟。

您将把每项工作分配给一名员工。
您可以将两项工作分配给同一名员工,在这种情况下,他/她完成这些工作所需的时间是他/她单独完成这些工作所需时间的总和。
如果您将工作分配给不同的员工,那么他们完成这些工作所需的时间是他们完成各自工作所需的时间中较长的一个。
找出完成作品所需的最短时间。

约束

  • 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

输出

打印完成作品所需的最短时间,以分钟为单位。


样本输入 1

3
8 5
4 4
7 9

示例输出 1

5

如果您将工作 A 分配给员工 2 和工作 B 给员工 1,他们将在 分别为 4 和 5 分钟。
由于您将工作分配给了不同的员工,因此需要 \max(4, 5) = 5 分钟两件作品完成。
不可能早点完成它们。


示例输入 2

3
11 7
3 2
6 7

示例输出 2

5

最好将两项工作分配给员工 2.
请注意,如果您将两项工作分配给同一名员工,则他/她完成这些工作所需的时间是他/她单独完成这些工作所需时间的总和。