#2937. [Poi2000]建造酿酒厂

内存限制:128 MiB 时间限制:1 Sec

题目描述

Abstinence岛上的居民很喜欢饮用纯酿的啤酒。迄今为止,他们都是从波兰进口啤酒,自己不生产。但今年岛上的一个城市决定建造一个酿酒厂,供给其他城市的啤酒需求。
岛上所有的城市都环绕在海岸线上,相邻两城之间用高速公路连接(也就是说,它们近似分布在一个圆上)。对于建造酿酒厂的城市来说,它将得到的信息是其余城市对于啤酒的日需求量,并且还有一张记载着相邻两城市之间距离的表格。经过计算,每一桶啤酒每英里的运费为一泰勒。每天的成本为所有城市的运费之和,前提是每个城市的日需求量必须得到满足。可以看出,日成本与酿酒厂建造位置是息息相关的。我们的问题是:为投资者找出最理想的酿酒厂位置,使得日成本最小。
 

输入格式

第一行包含一个数n,为城市数目,5<=n<=10000(我们假设城市已经沿着海边高速公路顺序编号,为12……n,对于1<=i<n,编号为i的城市的下一个城市为i+1,而n号城市的下一个城市为1号)。接下来的n行每行包含两个数字。第i+1行的两个数字为表示的是i号城市的日需求量,则表示i号城市与它的下一个城市之间的距离(单位:英里)。海边高速公路的总长度不大于1000000英里,所有城市啤酒的日需求量不大于1000

输出格式

 
仅包含一个数,为所求最小的日成本。

样例

样例输入


			
6
1 2
2 3
1 2
5 2
1 10
2 3

样例输出


			
41

数据范围与提示