B - Balanced Team Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はゲーム会社でチーム編成を担当しています。新しいプロジェクトのために、社員の中からチームメンバーを選ぶ必要があります。

会社には N 人の社員がおり、各社員には 1 から N までの番号が付けられています。

各社員には2つの能力値があります。社員 i のプログラミング能力は A_i 、デザイン能力は B_i です。

高橋君は、チームに入れる社員のグループを選ぶ必要があります。選んだグループに含まれる社員の集合を S としたとき、そのチームの「総合力」は以下のように定義されます：

  • S に含まれるすべての社員のプログラミング能力の合計と、デザイン能力の合計のうち、小さい方の値

プロジェクトを成功させるためには、プログラミングとデザインの両方がバランスよく必要です。そのため、総合力が高いチームを作りたいと考えています。

高橋君は、空でない社員のグループを選んだときの総合力として達成可能な最大値を求めたいです。

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
  • 1 行目には、社員の人数 N が与えられる。
  • 2 行目から N + 1 行目には、各社員の能力値が与えられる。
  • 1 + i 行目には、社員 i のプログラミング能力 A_i とデザイン能力 B_i が、スペース区切りで与えられる。

出力

総合力の最大値を 1 行で出力せよ。

入力例 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

Score : 300 pts

Problem Statement

Takahashi is in charge of team formation at a game company. He needs to select team members from the employees for a new project.

The company has N employees, numbered from 1 to N.

Each employee has two skill values. Employee i has programming ability A_i and design ability B_i.

Takahashi needs to select a group of employees to include in the team. Let S be the set of employees in the selected group. The "overall strength" of the team is defined as follows:

  • The minimum of the sum of programming abilities and the sum of design abilities of all employees in S

For the project to succeed, both programming and design skills are needed in a balanced manner. Therefore, he wants to form a team with high overall strength.

Takahashi wants to find the maximum achievable overall strength when selecting a non-empty group of employees.

Given the programming abilities and design abilities of the N employees, find the maximum value of the overall strength.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All inputs are integers

Input

N
A_1 B_1
A_2 B_2
:
A_N B_N
  • The first line gives the number of employees N.
  • From the 2nd line to the (N + 1)-th line, the skill values of each employee are given.
  • The (1 + i)-th line gives employee i's programming ability A_i and design ability B_i, separated by a space.

Output

Output the maximum value of the overall strength in one line.

Sample Input 1

3
3 5
4 2
2 6

Sample Output 1

9

Sample Input 2

4
10 1
1 10
3 3
2 4

Sample Output 2

16

Sample Input 3

8
12 7
5 18
20 4
3 15
9 9
14 6
2 25
11 8

Sample Output 3

76

Sample Input 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

Sample Output 4

1465

Sample Input 5

1
1000000000 1

Sample Output 5

1