Description

Farmer John 刚订购了大量干草捆。他希望把这些干草分成 $N$ 堆（$1 \le N \le 100{,}000$）围成一个圆，其中第 $i$ 堆应包含 $B_i$ 捆干草。不幸的是，运送干草的卡车司机在 John 提供这些信息时没有认真听，只记得把干草分成围成一圈的 $N$ 堆。送达后，John 发现第 $i$ 堆包含 $A_i$ 捆干草。显然，所有 $A_i$ 与所有 $B_i$ 的总和相同。

Farmer John 想把当前的分法（由 $A_i$ 描述）调整为目标分法（由 $B_i$ 描述）。将一捆干草从某一堆搬到沿圆周相距 $x$ 个位置的另一堆需要 $x$ 个单位的工作量。请帮助他计算所需的最小总工作量。

Input Format

第 $1$ 行：一个整数 $N$。

第 $2\cdots1+N$ 行：第 $i+1$ 行包含两个整数 $A_i$ 和 $B_i$（$1 \le A_i, B_i \le 1000$）。

4 
7 1 
3 4 
9 2 
1 13 

13 

Hint

圆周上共有 $4$ 堆。初始时，各堆分别包含 $7$、$3$、$9$、$1$ 捆干草。约翰希望将其调整为各堆分别包含 $1$、$4$、$2$、$13$ 捆干草。

所需最小工作量为 $13$（从第 $1$ 堆移动 $6$ 捆到第 $4$ 堆，从第 $3$ 堆移动 $1$ 捆到第 $2$ 堆，从第 $3$ 堆再移动 $6$ 捆到第 $4$ 堆）。