中考终于结束了！小z高兴地回到家中。可打开门，满屋子的书让他高兴不起来了。妈妈命令小z必须先整理书本再玩。经过中考的折磨，小z已经筋疲力尽了，于是他向你求助，请你帮他计算他最少需要花费多少力气。 书本分成若干堆，呈直线排布。每一堆的书本都有重量ｗ和价值ｖ。小z的任务是将所有书合成一堆。由于小z很看重书本的价值，所以他认为合并ｉ、ｊ两堆的书所需要的力气为w[i]-v[i]+w[j]-v[j]。合并后的书堆的重量和价值均为合并前两堆书的重量和价值的总和。也就是说，合并ｉ、ｊ两堆的书后，w=w[i]+w[j],v=v[i]+v[j]。小z不愿意走来走去，所以合并只能在相邻两堆书本间进行。书本合并前后，位置不变。如将1　2　3中的1、2进行合并，那么合并结果为3　3，再将3　3合并为6(1、2、3、6指重量)。

输入的第一行是一个整数n(2<=n<=500)。 第2～n+1行每行两个整数w和v(０

输出

输出共一行，这一行只有一个整数ｆ，表示最小力气。

样例输入

3
6 5
9 7
11 2

样例输出

15
【输入输出样例解释】
先将前两堆合并，所花的力气为：6-5+9-7=3, 合并成一堆的重量和价值为15 12，再将合并后书堆与剩余的一堆合并，所花力气为：15-12+11-2=12,一共花的力气是15。

来源/分类

 

[提交] [状态]