Contest Duration: - (local time) (100 minutes) Back to Home
B - Job Assignment /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

あなたの会社には従業員 1 から従業員 N までの N 人の従業員がいます。

あなたは仕事 A と仕事 B にそれぞれ従業員を 1 人割り当てます。

2 つの仕事が終わるのにかかる時間として考えられる最小の値を求めてください。

### 制約

• 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


### 出力

2 つの仕事が終わるのにかかる時間として考えられる最小の値 [分] を出力せよ。

### 入力例 1

3
8 5
4 4
7 9


### 出力例 1

5


2 つの仕事に異なる従業員を割り当てたので、2 つの仕事が終わるのにかかる時間は \max(4, 5) = 5 [分] となります。
これより短い時間で 2 つの仕事が終わることはありません。

### 入力例 2

3
11 7
3 2
6 7


### 出力例 2

5


Score : 200 points

### Problem Statement

Your company has N employees, called Employee 1 through N.
You have received two work orders, called Work A and B, which must be completed.
Employee i can complete Work A in A_i minutes and Work B in B_i minutes.

You will assign each work to one employee.
You can assign both works to the same employee, in which case the time it takes for him/her to complete them is the sum of the times it takes for him/her to do them individually.
If you assign the works to different employees, the time it takes for them to complete them is the longer of the times it takes for them to do their respective works.
Find the shortest possible time needed to complete the works.

### Constraints

• 2 \le N \le 1000
• 1 \le A_i \le 10^5
• 1 \le B_i \le 10^5
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_N B_N


### Output

Print the shortest possible time needed to complete the works, in minutes.

### Sample Input 1

3
8 5
4 4
7 9


### Sample Output 1

5


If you assign Work A to Employee 2 and Work B to Employee 1, they will complete them in 4 and 5 minutes, respectively.
Since you assigned the works to different employees, it will take \max(4, 5) = 5 minutes for the two works to be finished.
It is impossible to finish them earlier.

### Sample Input 2

3
11 7
3 2
6 7


### Sample Output 2

5


It is optimal to assign both works to Employee 2.
Note that if you assign both works to the same employee, the time it takes for him/her to complete them is the sum of the times it takes for him/her to do them individually.