题目描述

Abstinence 岛上的居民很喜欢饮用纯酿的啤酒。迄今为止，他们都是从波兰进口啤酒，自己不生产。但今年岛上的一个城市决定建造一个酿酒厂，供给其他城市的啤酒需求。

岛上所有的城市都环绕在海岸线上，相邻两城之间用高速公路连接（也就是说，它们近似分布在一个圆上）。对于建造酿酒厂的城市来说，它将得到的信息是其余城市对于啤酒的日需求量，并且还有一张记载着相邻两城市之间距离的表格。经过计算，每一桶啤酒每英里的运费为一泰勒。每天的成本为所有城市的运费之和，前提是每个城市的日需求量必须得到满足。可以看出，日成本与酿酒厂建造位置是息息相关的。我们的问题是：为投资者找出最理想的酿酒厂位置，使得日成本最小。

输入格式

第一行包含一个数 $n$，为城市数目，（我们假设城市已经沿着海边高速公路顺序编号，为 $1,2,\cdots,n$。对于 $1\le i<n$，编号为 $i$ 的城市的下一个城市为 $i+1$，而 $n$ 号城市的下一个城市为 $1$ 号）。

接下来的 $n$ 行每行包含两个数字表示 $i$ 号城市的日需求量与 $i$ 号城市与它的下一个城市之间的距离。海边高速公路的总长度不大于 $10^6$，所有城市啤酒的日需求量不大于 $10^3$。

输出格式

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

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

41

数据规模与约定

对于 $100\%$ 的数据，$5\le n\le 10^4$，