题目描述

农夫约翰刚刚订购了大量的干草。他想将它们组织成 $\red{N }$堆（$\red{1 <= N <= 100,000）}$，排列成一个圆圈，其中第 $\red{i }$堆包含 $\red{B_i }$捆干草。不幸的是，当农夫约翰提供这些信息时，运 送干草的卡车司机并没有仔细听，只记得把干草排成$\red{N}$堆排成一圈。交付后，$\red{Farmer John }$注意到堆 $\red{i }$包含 $\red{A_i }$捆干草。当然，$\red{A_i }$和 $\red{B_i }$的总和相同。

$\red{Farmer John }$想将干草捆从当前配置（由 $\red{A_i }$描述）移动到他想要的目标配置（由 $\red{B_i }$描述）。他需要 $\red{x }$个单位的工作才能将一个干草捆从一堆堆移到绕圆 $\red{x }$步远的 一堆。请帮助他计算他需要花费的最少工作量。

给出$\red{n}$块土地，现有泥土$\red{A[i]，}$需要改造成$\red{B[i]，}$但这次土地排列成环，且不可买进买出，只能运，且$\red{∑A[i]=}$$\red{∑B[i]，}$问最小花费。

输入格式

第 $\red{1 }$行：单个整数 $\red{N}$。

第 $\red{2..1+N }$行：第 $\red{i+1 }$行包含两个整数 $\red{A_i }$和 $\red{B_i (1 <= A_i, B_i <= 1000)}$。

输出格式

无

样例

输入样例

4 
7 1 
3 4 
9 2 
1 13

输出样例

13

提示

一圈有$\red{4}$堆。最初，这些堆包含 $\red{7}$、$\red{3}$、$\red{9 }$和 $\red{1 }$包干草。农夫约翰想移动它们，使这些堆包含 $\red{1}$、$\red{4}$、$\red{2 }$和 $\red{13 }$包干草。

至少需要 $\red{13 }$个单位的工作（将 $\red{6 }$包从第 $\red{1 }$堆移到第 $\red{4 }$堆，将 $\red{1 }$包从第 $\red{3 }$堆移到第 $\red{2 }$堆，将 $\red{6 }$包从第 $\red{3 }$堆移到第 $\red{4 }$堆）。