砍树

题目描述:

      在遥远的cc王国，有一个山坡。山坡上有N棵树。这些树严重影响了cc王国平民的进出，生活。所以，cc国王决定砍掉这些树！为了不浪费资源，所有的树砍倒后都必须运输到工厂。现在只有一个工厂在山脚下，但cc国王可以在山上再建两座工厂。cc国王现在有点穷，他想知道建两座工厂在山上得到的最小的运输费用是多少？假定运输一公斤木头一米需要一元钱，而且树只能往山下运输。

输入格式:

      输入的第一行为一个正整数n表示树的个数 (2≤n≤100000)。树从山顶到山脚按照1,2,...,n标号。

      接下来n行，每行有两个正整数（用空格分开）。

      最后一颗树的d_n​，表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用在2^63-1范围内。

输出格式:

      输出最小的运输费用。

样例输入:

6
1 4
3 5
2 4
7 7 
6 9
4 5

样例输出:

68

提示:

      对于30%的数据，n<=200;

      对于50%的数据，n<=1000，Wi,Di<=100;

      对于100%的数据，n<=100000，Wi,Di<=1500.

      样例解释（黑点的表示建工厂）：

 

      最小值为：1*（4+5+4）+3*（5+4）+2*4+7*0+6*0+4*5=13+27+8+0+0+20=68.

时间限制: 1000ms
空间限制: 256MB

---

来源: by zhr（一个蒟蒻）