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