【USACO】奶牛叠罗汉
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有n头奶牛，每头奶牛有两个属性：重量w和强壮度s。现在这些奶牛要玩一个叠罗汉的游戏，即一头奶牛要站在另一头奶牛的背上。最后只有一头奶牛站在地面上，从上到下刚好有n层。这时候，奶牛的难受值为它背上的奶牛重量之和减去它自己的强壮度。难受值的最小值为0. 请问，要如何安排奶牛叠罗汉的顺序，才能使最难受的奶牛的难受值最小。
输入格式
第一行，一个正整数，表示n。 接下来有n行，每行两个整数，分别表示一头奶牛的重量和强壮度。
输出格式
一个整数，表示最难受的奶牛的最小难受值。
样例
输入样例
5
4 3
2 5
1 9
4 8
10 10
输出样例
1
数据范围与提示
$ n\leq 5*10^4,1 \leq s \leq 10^4,1 \leq w \leq 10^9 $