题目描述

给定 $n$ 对数字 $(w_1,s_1), \dots, (w_n,s_n)$，请为这些数对重新安排一个合理的顺序，使得最大的 $a_i$ 尽可能小，输出这个值。

$a_i$ 定义为 $w_1+w_2+\dots+w_{i-1}-s_i$，也就是该数对前的所有 $w$ 之和与本数对的 $s$ 之差。

输入格式

• 第一行：单个整数 $n$
• 第二行到第 $n+1$ 行：每行两个整数表示 $w_i$ 与 $s_i$

输出格式

• 单个整数：表示最大的 $a_i$ 的最小值。

3
10 1
5 5 
1 8

5

样例解释 1

重新安排的顺序应该是 1 8 5 5 10 1

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 100$，$1\leq w_i, s_i\leq 100$；
• 对于 $60\%$ 的数据，$1\leq n\leq 20,000$，$1\leq w_i, s_i\leq 10,000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 300,000$，$1\leq w_i, s_i\leq 10^9$。