分数: 300 分
问题陈述
高桥在一家游戏公司负责团队组建。他需要从员工中为新项目选择团队成员。
公司有 N 员工,编号自 1 to N.
每个员工都有两个技能值。员工 i 具有编程能力 A_i 及设计能力 B_i.
Takahashi 需要选择一组员工加入团队。让 S 是所选组中的一组员工。团队的“整体实力”定义如下:
- 年度内所有员工编程能力总和与设计能力总和的最小值 S
为了使项目取得成功,需要平衡地兼顾编程和设计技能。因此,他想要组建一支综合实力较高的团队。
Takahashi 希望在选择非空员工组时找到可实现的最大综合实力。
鉴于编程能力和设计能力 N 员工,求综合实力的最大值。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 所有输入均为整数
输入
N A_1 B_1 A_2 B_2 : A_N B_N
- 第一行给出员工人数 N.
- 从第 2 行到 (N + 1)第行,给出了每个员工的技能值。
- 的 (1 + i)-th 行给员工 i的编程能力 A_i 及设计能力 B_i,用空格分隔。
输出
输出一行中综合实力的最大值。
示例输入 1
3 3 5 4 2 2 6
示例输出 1
9
示例输入 2
4 10 1 1 10 3 3 2 4
示例输出 2
16
示例输入 3
8 12 7 5 18 20 4 3 15 9 9 14 6 2 25 11 8
示例输出 3
76
示例输入 4
20 100 40 35 120 80 75 60 10 15 95 200 30 45 55 70 150 25 25 90 20 10 180 160 60 55 65 30 110 140 35 75 85 5 250 125 45 95 100 50 70
示例输出 4
1465
示例输入 5
1 1000000000 1
示例输出 5
1