/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
あなたの会社には従業員 1 から従業員 N までの N 人の従業員がいます。
今あなたは仕事 A と仕事 B の 2 つの仕事を受注したので、これらを完了しなければなりません。
従業員 i は仕事 A を A_i 分、仕事 B を B_i 分でこなすことができます。
あなたは仕事 A と仕事 B にそれぞれ従業員を 1 人割り当てます。
同じ従業員を両方の仕事に割り当てても構いませんが、その場合 2 つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となります。
仕事 A と仕事 B に異なる従業員を割り当てた場合、2 つの仕事が終わるのにかかる時間は、各仕事が終わるのにかかる時間の長い方となります。
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
仕事 A には従業員 2 を、仕事 B には従業員 1 を割り当てると、仕事 A, B はそれぞれ 4, 5 分で完了します。
2 つの仕事に異なる従業員を割り当てたので、2 つの仕事が終わるのにかかる時間は \max(4, 5) = 5 [分] となります。
これより短い時間で 2 つの仕事が終わることはありません。
入力例 2
3 11 7 3 2 6 7
出力例 2
5
両方の仕事に従業員 2 を割り当てるのが最適です。
同じ従業員を両方の仕事に割り当てた場合 2 つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となることに注意してください。
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.