奶牛玩杂技 Cow Acrobats

题目背景

农夫约翰的奶牛们打算加入马戏团。它们尝试走钢丝、荡秋千和钻入大炮都不成功，于是决定练习叠罗汉：把所有奶牛竖直地叠在一起。

题目描述

共有 N 头奶牛，第 i 头的体重为 W_i，力量为 S_i。每头牛的风险值等于它上方所有奶牛的体重之和减去它自己的力量，不包括自身重量。

请安排所有奶牛从上到下的顺序，使所有奶牛中最大的风险值尽可能小。风险值可以为负数。

输入格式

第一行一个整数 N。 随后 N 行，每行两个整数 W_i、S_i。

输出格式

输出一个整数，表示所有排列中最小的最大风险值。

数据范围

1 ≤ N ≤ 50000，1 ≤ W_i ≤ 10000，1 ≤ S_i ≤ 1000000000。

样例解释

把体重为10的奶牛放在最下面，它承担另外两头牛，风险为2+3−3=2，其余奶牛的风险更小。

样例 1

3
10 3
2 5
3 3

2