C - 魔法使い高橋君

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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

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

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

制約

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

入力

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

N
a_1 b_1
:
a_N b_N

出力

X の最小値を出力せよ。


入力例1

1
10 20

出力例1

10

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


入力例2

2
30 20
10 20

出力例2

20

2 番目の魔法、1 番目の魔法の順に唱えると、気温は 010-10200 度と変化します。


入力例3

5
5 10
10 5
10 15
15 10
20 20

出力例3

10

例えば、13524 番目の魔法の順に唱えればよいです。