题目描述

$N$ 头奶牛要摞成一摞：从下到上排成 $N$ 层，每层恰好一头奶牛，$N$ 头奶牛都要用到。

第 $i$ 头奶牛的体重为 $W_i$，力量为 $S_i$。

记奶牛 $i$ 上方所有奶牛的体重之和为 $W'_i$（不包括奶牛 $i$ 自己的体重；被放在最上面的奶牛满足 $W'_i = 0$），则奶牛 $i$ 的压扁指数为

（压扁指数可以为负数，表示上方压着它的重量还不及它自己的力量。）

一摞奶牛的总压扁指数，定义为所有奶牛压扁指数中的最大值：

请你决定这 $N$ 头奶牛从下到上的排列顺序，使得总压扁指数 $C$ 最小，并输出这个最小值。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $W_i$ 与 $S_i$，中间用一个空格隔开，依次表示编号为 $i$ 的奶牛的体重与力量。

输出格式

一行一个整数，表示总压扁指数的最小值。

注意：总压扁指数可能为负数。

样例 1

3
10 3
2 5
3 3

2

样例解释

一种最优排列（从下到上）为：$(W_1,S_1)=(10,3)$、$(W_2,S_2)=(2,5)$、$(W_3,S_3)=(3,3)$。

• 最上方的奶牛：上方体重之和 $W' = 0$，压扁指数 $0 - 3 = -3$；
• 中间的奶牛：上方体重之和 $W' = 3$，压扁指数 $3 - 5 = -2$；
• 最下方的奶牛：上方体重之和 $W' = 3 + 2 = 5$，压扁指数 $5 - 3 = 2$。

三者取最大值，得到总压扁指数 $2$；不存在使总压扁指数小于 $2$ 的排列。

数据范围与约定

• $1 \le N \le 5 \times 10^4$
• $1 \le W_i \le 10^4$
• $1 \le S_i \le 10^9$
• 保证答案在 $32$ 位有符号整数范围内 1 ≤ Wi ≤ 10^4
  1 ≤ Si ≤ 10^9

样例

输入：
3
10 3
2 5
3 3

输出：
2