配点 : $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$ つの仕事が終わるのにかかる時間として考えられる最小の値 [分] を出力せよ。

3
8 5
4 4
7 9

5

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

3
11 7
3 2
6 7

5

両方の仕事に従業員 $2$ を割り当てるのが最適です。 同じ従業員を両方の仕事に割り当てた場合 $2$ つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となることに注意してください。