Farmer John は大量の干し草の束を注文し、環状の $N$ 山（$1 \le N \le 100,000$）にして、山 $i$ に $B_{i}$ 束置きたいと考えました。しかし運転手はよく聞かず、環状の $N$ 山だけ覚えていました。配送後の山 $i$ は $A_{i}$ 束です。もちろん $A_{i}$ と $B_{i}$ の合計は同じです。

現在の $A_{i}$ の配置から目標の $B_{i}$ へ移動します。環に沿って $x$ 歩離れた山へ一束動かす仕事量は $x$ です。最小仕事量を求めてください。

入力

• 第 $1$ 行：整数 $N$。

• 第 $2..1+N$ 行：第 $i+1$ 行は整数 $A_{i}$ と $B_{i}$（$1 \le A_{i}, B_{i} \le 1000$）です。

出力

入出力例

入力 1

4
7 1
3 4
9 2
1 13

出力 1

13

注記

環状の $4$ 山の最初の束数は $7$、$3$、$9$、$1$、目標は $1$、$4$、$2$、$13$ です。

最小仕事量 $13$ は、山 $1$ から $4$ へ $6$ 束、山 $3$ から $2$ へ $1$ 束、山 $3$ から $4$ へ $6$ 束動かせば達成できます。

問題作成者：Brian Dean、2012