时间限制：1秒　　内存限制：256M

---

【题目描述】

　　牧场公路的沿途分布着 \(n\) 个草场，沿途顺次编号 \(1..n\)，公路的尽头就是牧场总部。
　　草场每天生产的牧草都要运往干草厂加工。目前在牧场总部有一个干草厂，牧场主打算再新建两个干草厂，现在需要你确定干草厂建造的位置，使得每天花在干草运输的总费用最小（干草的运输费用是1元/公里•千克）。

【输入格式】

　　第一行为一个正整数 \(n\)，表示草场个数，沿途顺次编号为 \(1,2,…,n\)。
　　接下来 \(n\) 行，每行有两个正整数 \(w_i\ d_i\)。\(w_i\) 表示第 \(i\) 个牧场每天生产干草质量（单位：千克），\(d_i\) 表示第 \(i\) 个牧场与第 \(i+1\) 个牧场的距离（单位：公里）。最后一个数 \(d_n\)，表示第 \(n\) 个草场到牧场总部的距离。

【输出格式】

　　输出一个整数，表示最小运输费用。

【输入输出样例】

　Input

8
2 1
1 3
2 3
1 2
1 1
5 4
2 1
1 2

　Output

23

【数据限制】

　　\(100\%\) 的数据满足：\(2≤n≤20 0000\)，\(1≤w_i≤10 000\)，\(0≤d_i≤10 000\)

【来源】

　　Mr.he