题目描述

小 A 想把他满屋子的书整理一下。为了应付繁重的学习任务，小 A 已经筋疲力尽了，于是他向你求助，请你帮他计算最少需要花费多少力气。 书本分成若干堆，呈直线排布。每一堆的书本都有重量 $w$ 和价值 $v$ 。小 A 的任务是将所有书合成一堆。因为小 A 很看重书本的价值，所以他认为合并 $i$，$j$ 两堆的书所需要的力为 $w_i-v_i+w_j-v_j$ 。合并后的书堆的重量和价值均为合并前两堆书的重量和价值的总和。也就是说，合并 $i$，$j$ 两堆的书后，$w=w_i+w_j$，$v=v_i+v_j$。小 A 不愿意走来走去，所以合并只能在相邻两堆书本间进行。书本合并前后，位置不变。如果将 $1$，$2$，$3$ 中的 $1$，$2$ 进行合并，那么合并结果为 $3$，$3$，再将 $3$，$3$ 合并为 $6$（ $1，2，3，6$ 指重量）。

输入格式

第一行是一个整数 $n$ ($2 \le n \le 400$)；

第2$\sim n+1$ 行每行两个整数 $w_i$ 和 $v_i$ ( $0 \lt v_i \lt w_i \le 1000$)。

输出格式

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

样例

3
6 5
9 7
11 2

15

样例解释

先将前两堆合并，再将合并后的书堆与剩余的一堆合并。