Boxes

题目描述

Orange有许多装满东西的宝箱，某天，Orange心血来潮，决定整理这些宝箱。在整理过程中，Orange决定重新修复并加固这些宝箱，因为它们经过长期存放后变得破旧不堪。当Orange要修复一个宝箱时，他应该先把要修复宝箱中的所有物品挪到其他箱子的空余空间中(假定箱子中的物品是可分的），让后将这个箱子进行加固。由于各个箱子的材质不同，他们升级后的容量有的会变大，有的会变小。对于第 $i$ 个箱子，他的容量升级前后分别为 $a_i$ 和 $b_i$。

由于Orange的强迫症，在升级所有箱子的过程中，他不想有任何物品被放到地上（物品只能从一个箱子移动到另一个箱子中，且存在容量限制），Orange显然需要一个额外的箱子来中转一些物品（或者存放额外的物品）。Orange想知道，这个额外的箱子最小的容量应该是多少？

注意，Orange只在意物品被放入箱子中，并不在意物品所属的箱子，这意味着升级后，箱子1中的物品可能在其他箱子中。

输入格式

输入第一行为一个整数 $n$，表示箱子个数。 接下来 $n$ 行，每行2个整数 $a_i$ 和 $b_i$。

数据范围

$n \le 10^6$ $a_i,b_i \le 10^9$

输出格式

输出一个整数，表示答案。

样例 #1

样例输入 #1

5
3 3
3 2
1 5
2 3
5 1

样例输出 #1

1

提示

样例解释1

考虑按照如下策略操作： 使用一个大小为1的空箱子$B_0$，其他箱子依次记为 $B_i$。

1. 把$B_3$的物品全部放入当前空箱子，然后升级B_#，再把$B_0$中1个单位的物品放入升级后的$B_3$，此时$B_0$剩余容量为1，$B_3$剩余容量为4。
2. 把$B_4$的物品放入到新的$B_3$，此时 $B_3$ 剩余容量为2，等$B_4$升级后，此时$B_0,B_3,B_4$剩余容量分别为1，2，3。
3. 此时把$B_1$的3个物品放入$B_4$，再升级$B_1$，此时$B_0,B_1,B_3$剩余容量分别为1，3，2。
4. 此时，把$B_2$的物品放入$B_0$和$B_3$，然后升级$B_2$，此时$B_1,B_2$的剩余容量分别为3, 2。
5. 最后把$B_5$的物品放入$B_1,B_2$，升级$B_5$，至此，所有箱子升级完成。