問題文

高橋君は $N$ 個の魔法を覚えています。魔法は $1$ から $N$ まで番号が振られています。

最初、気温は $0$ 度です。高橋君が $i$ 番目の魔法を唱えると、気温が $a_i$ 度だけ上がった後 $b_i$ 度だけ下がります。

高橋君はすべての魔法をちょうど $1$ 回ずつ唱えます。この間の気温の最大値を $X$ 度とします。高橋君は魔法を唱える順番を工夫して、$X$ をできるだけ小さくしようとしています。$X$ の最小値を求めてください。

制約

• $1≦N≦10^5$
• $a_i$，$b_i$ は整数である。
• $1≦a_i，b_i≦10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ $:$ $a_N$ $b_N$

出力

$X$ の最小値を出力せよ。

入力例1

1
10 20

出力例1

10

唯一の魔法を唱えると、気温は $0$ → $10$ → $\-10$ 度と変化します。

入力例2

2
30 20
10 20

出力例2

20

$2$ 番目の魔法、$1$ 番目の魔法の順に唱えると、気温は $0$ → $10$ → $\-10$ → $20$ → $0$ 度と変化します。

入力例3

5
5 10
10 5
10 15
15 10
20 20

出力例3

10

例えば、$1$，$3$，$5$，$2$，$4$ 番目の魔法の順に唱えればよいです。