题目描述

代码岛的居民们想建一个自己的可乐工厂。岛上所有的城市都是以环状分布在海边。可乐厂的工人知道每天各城市消费的可乐桶数。另外还知道相邻城市之间的距离。每桶可乐每英里的运费是 \(1\) 元。日运费是将所需要的可乐从工厂运到所有城市所必需的运费之和。日运费的多少和可乐厂的位置有关。工人们想找到一个合适的城市来修建厂房，以使得日运费最小。

请设计一个程序读入城市的数目、相邻两城市间的距离以及每个城市消费的可乐桶数，计算最小的日运费。

格式

输入格式

第一行是一个整数 \(n（5 <= n <= 10000）\) ，表示城市的数目。 城市沿高速路编号，使得相邻的城市的编号也相邻（城市 \(1\) 和 \(n\) 也被认为是相邻）。 以下的 \(n\) 行，每行有两个非负整数。第 \(i+1\) 行的数 \(z_i、d_i\) 分别是城市 \(i\) 每日的可乐消费量（桶）和从城市I沿高速路到下一个城市的距离（英里）。高速路的总长不会超过 \(1000000\) 英里。每座城市的日消费量不会超过 \(1000\) 桶。

输出格式

一个整数，表示所需的最小日运费。

样例1

样例输入1

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

样例输出1

41

来源

地址：\(\text{Online~Judge}\)
作者：征宇
模拟赛\(T4\)