题目描述

农夫约翰的$N$头奶牛（编号$1$到$N$）计划逃离农场加入马戏团。由于它们的蹄子无法走钢丝或荡秋千（上次尝试用大炮发射奶牛也以失败告终），它们决定练习表演杂技叠罗汉。

这些奶牛缺乏创意，只想到一种表演方式：垂直叠成一摞。现在它们需要决定叠罗汉的顺序。

每头奶牛有两个属性：

• 重量$W_i（1 ≤ W_i ≤ 10,000）$
• 力量$S_i（1 ≤ S_i ≤ 1,000,000,000）$

奶牛承受的风险值定义为：它上方所有奶牛的重量之和（不包括它自身）减去它的力量值（力量越大风险越小）。你的任务是确定一个叠放顺序，使得所有奶牛中最大的风险值尽可能小。

输入格式

• 第$1$行：一个整数$N$（奶牛数量）
• 第$2$到$N+1$行：每行两个整数$W_i和S_i$，表示第$i$头奶牛的重量和力量

输出格式

• 第$1$行：一个整数，表示最优排列下所有奶牛中的最大风险值

输入样例

3
10 3
2 5
3 3

输出样例

2

提示

输出解释： 将重$10$的奶牛放在最下面。它将承受上方两头奶牛的重量$（2+3=5）$，风险值为$5-3=2$。其他奶牛的风险值更小。

来源

USACO 2005年11月银组