问题描述

具体描述见教材p261： 小A想把他满屋子的书整理一下。书本分成若干堆。每一堆的书本都有质量u和价值t。小A的任务是将所有书合成一堆。因为小 A 认为合并 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指质量)。请你帮他计算最少需要花费多少力气。

格式

输入

第1行是一个整数 n(2≤n≤400)； 第2~n+1行每行两个整数 w 和 v (0<v<w≤1000)。

输出

仅1行，只有一个整数，表示花费的最少力气。

样例说明： 先将前两堆合并，再将合并后的书堆与剩余的一堆合并。

样例

3
6 5
9 7
11 2

15

限制

1s, 64MB.