题目描述

农场主约翰的 $N（1\le N\le 50,000)$ 头奶牛（编号为 $1$ 到 $N$ ）计划逃跑并加入马戏团。它们的蹄子使得它们无法走钢丝和荡秋千（而且它们上次尝试把一头奶牛从大炮中发射出去时，结果惨不忍睹）。因此，它们决定练习表演杂技。

奶牛们的创意不多，只想出了一个杂技：相互站在对方身上形成一个垂直的叠罗汉。奶牛们试图弄清楚它们在这个叠罗汉中应该按什么顺序排列。

每头奶牛都有一个对应的重量 $（1\le W_i\le 10,000）$ 和力量 $（1\le S_i \le 10^9）$。奶牛崩塌的风险等于所有站在它上面的奶牛的总重量（不包括她自己的重量）减去她的力量（所以力量更大的奶牛风险更小）。你的任务是确定一种排列顺序，使得任何奶牛的最大崩塌风险最小。

输入格式

• 第1行：一个整数N。
• 第2行到第 $N+1$行：第 $i+1$行描述第 $i$头奶牛的两个用空格分隔的整数，$W_i$ 和 $S_i$。

输出格式

第1行：一个整数，表示在任何最优排列中所有奶牛的最大风险值。

3
10 3
2 5
3 3

2

3
1 6
4 2
2 3

0

数据规模与约定