1362: 整理书本

ztc想把他满屋子的书整理一下。为了应付繁重的学习任务，ztc已经筋疲力尽了，于是他向你求助，请你帮他计算他最少需要花费多少力气。

书本分成若干堆。呈直线排布。每一堆的书本都用重量w和价值v。ztc的任务是将所有书合成一堆。因为ztc很看重书本的价值，所以他认为合并i，j两堆的书所需要的力气为w[i]-v[i]+w[j]-v[j]。合并后的书堆的重量和价值均为合并前两堆书的重量和价值的总和。也就是说，合并i，j两堆的书后，w=w[i]+w[j],v=v[i]+v[j]。小智个人不愿意走来走去，所以合并只能在相邻两堆书本间进行。书本合并前后，位置不变。如将1，2，3中的1，2进行合并，那么合并结果为3，3，再将3，3合并为6（1，2，3，6指重量）。

第一行是一个整数n(2≤n≤400)

第2~n+1行每行两个整数w和v（0＜v<w≤1000)

3
6 5
9 7
11 2

15