题目描述

农夫约翰刚刚订购了大量草堆。他希望将这些草堆组织成 $N$ 堆（$1 \leq N \leq 100,000$），围成一个圆环，其中第 $i$ 堆包含 $B_i$ 个草堆。不幸的是，送草的卡车司机在约翰提供信息时没有认真听，只记得要把草堆围成一个圆环。货物交付后，约翰注意到第 $i$ 堆包含 $A_i$ 个草堆。当然，$A_i$ 和 $B_i$ 的总和相等。

约翰希望将目前的草堆配置（由 $A_i$ 描述）移动到他期望的目标配置（由 $B_i$ 描述）。他花费 $x$ 单位的工作来将一堆草堆从一个与圆环相差 $x$ 步的位置移动到另一个堆中。请帮他计算他需要花费的最少工作量。

简易题面

给出 $n$ 块土地，现有泥土 $A_i$，需要改造成 $B_i$，但这次土地排列成环，且不可买进买出，只能运，且 $\sum A_i=\sum B_i$，问最小花费。

输入格式

• 第一行：一个整数 $N$。
• 第二行到第 $1+N$ 行：第 $i+1$ 行包含两个整数 $A_i$ 和 $B_i$（$1 \leq A_i, B_i \leq 1000$）。

输出格式

一个整数，表示约翰需要花费的最少工作量。

示例

输入

4 
7 1 
3 4 
9 2 
1 13

输出

13

提示

共有 $4$ 堆草围成一个圆环。

最初，这些堆包含 $7,3,9$ 和 $1$ 个草堆。 约翰希望把它们移动到目标堆包含 $1,4,2$ 和 $13$ 个草堆。

约翰需要至少移动 $13$ 个单位的工作（将 $6$ 个草堆从第 $1$ 堆移动到第 $4$ 堆，将 $1$ 个草堆从第 $3$ 堆移动到第 $2$ 堆，将 $6$ 个草堆从第 $3$ 堆移动到第 $4$ 堆）。