問題文

高橋君は 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

入力例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 番目の魔法の順に唱えればよいです。