← 返回题目列表

AtCoder · awc0103_b

B. 平衡的团队

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

分数: 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