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