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

---

【题目描述】

　　从山顶到山脚下的路边种有 \(n\) 颗老树，当地政府决定砍伐这些树木。出于不浪费木材的考虑，每棵树都要运往一个锯木厂加工。

　　砍伐后的树木只能从山上向山下运输。山脚下有一家锯木厂。沿途还可以再建两座锯木厂。现在需要你确定锯木厂建造的位置，使得木材的总运输费用最小（木材的运输费用是 1元/米•千克。）

　　编写一个程序，读入树木的数目，重量和位置，计算最小的运输费用输出结果。

【输入格式】

　　第一行为一个正整数 \(n\)，表示树木的数量。树从山顶到山脚按照 \(1,2,…,n\) 标号。
　　接下来 \(n\) 行，每行有两个正整数 \(w_i\ d_i\)。\(w_i\) 表示第 \(i\) 棵树的重量（单位：千克），\(d_i\) 表示第 \(i\) 棵树和第 \(i+1\) 棵树之间的距离。最后一个数 \(d_n\)，表示第 \(n\) 棵树到山脚的锯木厂的距离。

【输出格式】

　　输出包含一个整数：最小运输费用。

【输入输出样例】

　Input

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

　Output

26

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤n≤20 000\)，\(1≤ w_i ≤10 000\)，\(0≤d_i≤10 000\)

【来源】

　　Mr.he**