小 D は世界一周旅行の準備をしています。出発前に、計画に従ってリストにある $n$ 個の物資準備操作を完了する必要があり、これらの操作には最初、順番に $1, 2, \dots, n$ の番号が付けられています。

現在の物資の数量を整数 $x$ とし、初期状態では $x = 0$ です。$i$ 番目の操作は 2 つの正の整数 $a_i, b_i$ によって記述され、この操作を実行すると順番に次の変化が起こります：

1. まず $x$ を $a_i$ 増やす（すなわち $x \leftarrow x + a_i$ とする）。
2. 次に $x$ の大きさを確認する：このとき $x > b_i$ であれば、$x$ を $b_i$ まで減らす（すなわち $x \leftarrow \min(x, b_i)$ とする）。

操作の実行を開始する前に、小 D はリストの順序に対して高々 1 回の調整を行うことができます。すなわち、操作を 1 つ任意に選んで取り出し、列の末尾へ移動させ、残りの操作の相対的な順序はそのままにします（調整を一切行わないことも選べます）。

調整が終わった後、小 D は新しい順序で前から後ろへと $n$ 個の操作をすべて順番に、各操作をちょうど 1 回ずつ実行します。小 D は、すべての操作を実行し終えた後の物資の数量 $x$ としてあり得る最大値がいくつになるかを知りたいです。

入力

stdin からデータを読み込む。

1 行目には、操作の個数を表す正の整数 $n$ が与えられる。

続く $n$ 行のうち $i$ 行目には、$i$ 番目の操作のパラメータを表す 2 つの正の整数 $a_i, b_i$ が与えられる。

出力

stdout に出力する。

すべての操作を実行し終えた後の物資の数量 $x$ の最大可能値を表す整数を 1 行で出力せよ。

入出力例

入力 1

3
1 100
100 90
1 1

出力 1

90

注記

$2$ 番目の操作を列の末尾に移動すると、操作の実行順序は $1, 3, 2$ となります。各操作の実行が完了するごとに、$x$ の値は順に $1, 1, 90$ へと変化します。

もし $1$ 番目の操作を末尾に移動すると最終的な値は $x = 2$ となり、順序を調整しない場合や $3$ 番目の操作を末尾に移動する場合は最終的な値は $x = 1$ となります。したがって、$x$ の最大可能値は $90$ です。

入出力例 2

競技者ディレクトリ内の supply/supply2.in および supply/supply2.ans を参照せよ。

この例はテストケース $1 \sim 4$ の制約条件を満たす。

入出力例 3

競技者ディレクトリ内の supply/supply3.in および supply/supply3.ans を参照せよ。

この例はテストケース $5 \sim 6$ の制約条件を満たす。

入出力例 4

競技者ディレクトリ内の supply/supply4.in および supply/supply4.ans を参照せよ。

この例はテストケース $7 \sim 10$ の制約条件を満たす。

制約

すべてのデータについて、$1 \le n \le 2 \times 10^5$、$1 \le a_i, b_i \le 10^9$ が保証される。注意：データにおいて $a_i \le b_i$ は保証されない。

本問題には全部で $10$ 個のテストケースがあり、各テストケースは $10$ 点で、それぞれ独立に採点される。詳細な制約は以下の表の通りである。

特殊性質 A：$b_1 = b_2 = \dots = b_n$。