Farmer John の $N$ 頭の牛（$1 \le N \le 50{,}000$、番号 $1..N$）は逃げ出してサーカスに入る計画です。蹄があるため綱渡りや空中ブランコはできません（前回の大砲で牛を飛ばす試みも惨敗しました）。そこで曲芸を練習することにしました。

牛たちは創造力に乏しく、互いの上に立ってある高さの縦の塔を作る芸しか思い付きませんでした。塔の中の順序を考えています。

各牛には重さ（$1 \le W_i \le 10{,}000$）と力（$1 \le S_i \le 1{,}000{,}000{,}000$）があります。倒れる危険度は、上の牛の総重量（自分を除く）から力を引いた値です（強いほど危険度が低くなります）。全牛の最大危険度を最小化する順序を求めてください。

入力

• 1 行目：整数 $N$。
• $2..N+1$ 行目：$i+1$ 行目に牛 $i$ の空白区切りの整数 $W_i$ と $S_i$。

出力

• 1 行目：危険度を最小化する任意の最適順序における、全牛の最大危険度を表す整数。

入出力例

入力 1

3
10 3
2 5
3 3

出力 1

2

注記

重さ 10 の牛を下に置きます。他の二頭を支えるので危険度は $2+3-3=2$ です。他の牛の危険度はこれより低くなります。