5415. 耍杂技的牛
时间限制：1000 MS 内存限制：256 MB
题目描述
# 耍杂技的牛 ## 题目描述 农民约翰的 $N$ 头奶牛（编号为 $1$ 到 $N$）计划逃跑并加入马戏团。为此，它们决定练习叠罗汉：奶牛们站在彼此的身上，形成一个高高的垂直堆叠。 第 $i$ 头奶牛的重量为 $W_i$，强壮程度为 $S_i$。一头奶牛的**风险值**定义为它上方所有奶牛的重量之和减去它自身的强壮程度，不计它自身的重量。风险值可以为负数，且风险值越大，这头奶牛支撑不住的可能性就越高。 请你安排这 $N$ 头奶牛从上到下的顺序，使所有奶牛风险值中的最大值尽可能小，并求出这个最大风险值的最小可能值。 ## 输入格式 从文件 `cows.in` 中读入数据。 第一行包含一个整数 $N$，表示奶牛的数量。 接下来 $N$ 行，每行包含两个整数 $W_i$ 和 $S_i$，表示第 $i$ 头奶牛的重量和强壮程度。 ## 输出格式 将结果输出到文件 `cows.out` 中。 输出一个整数，表示所有排列中最大风险值的最小可能值。 ## 数据范围 - $1 \le N \le 50000$。 - $1 \le W_i \le 10000$。 - $1 \le S_i \le 1000000000$。 ## 样例输入 ``` 3 10 3 2 5 3 3 ``` ## 样例输出 ``` 2 ``` ## 样例说明 将奶牛按编号 $3, 2, 1$ 从上到下排列时，三头奶牛的风险值依次为： - 第 $3$ 头奶牛：$0-3=-3$。 - 第 $2$ 头奶牛：$3-5=-2$。 - 第 $1$ 头奶牛：$(3+2)-3=2$。 最大风险值为 $2$，且不存在最大风险值更小的排列。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 空间限制：$256$ MB。