0x08基本算法（练习）10：耍杂技的牛

P1842 [USACO05NOV] 奶牛玩杂技

题目

有 $N$ 头牛，每头牛都有自己的体重以及力量，编号为 $i$ 的奶牛的体重为 $W_i$，力量为 $S_i$。

所有牛都参与叠罗汉的游戏，第一头牛站在第二头的身上， 同时第二头牛又站在第三头牛的身上...最底下的是第 $N$ 头牛。

当某头牛身上站着另一些牛时它就会在一定程度上被压扁，我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去它的力量。奶牛们按照一定的顺序摞在一起后， 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。

你的任务就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $W_i$ 和 $S_i$。

输出格式

一行一个整数表示最小总压扁指数。

输入输出样例 #1

输入 #1

3
10 3
2 5
3 3

输出 #1

2

说明/提示

对于 $100\%$ 的数据，$1 \le N \le 5\times 10^4$，$1 \le W_i \le 10^4$，$1 \le S_i \le 10^9$。