题目描述

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

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

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

输入格式

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

第 ${2..1+N }$行：第 ${i+1 }$行包含两个整数 ${A_i }$和 ${B_i (1 <= A_i, B_i <= 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 }$堆）。