P17770 物资准备

小 D 正在筹备一场环球旅行。出发前，他需要按计划完成清单上的 $n$ 项物资准备操作，这些操作初始时按顺序编号为 $1, 2, \ldots, n$。 记当前的物资数量为整数 $x$，初始时 $x = 0$。第 $i$ 项操作由两个正整数 $a_i, b_i$ 描述，执行该操作时会依次发生以下变化： 1. 先将 $x$ 增加 $a_i$（即令 $x \leftarrow x + a_i$）； 2. 随后检查 $x$ 的大小：若此时 $x > b_i$，则将 $x$ 削减至 $b_i$（即令 $x \leftarrow \min(x, b_i)$）。 在开始执行操作前，小 D 可以对清单顺序进行**至多一次调整**：任选其中一项操作，将其取出并移至序列的末尾，其余操作的相对顺序保持不变（也可以选择不进行任何调整）。 调整完毕后，小 D 将按新顺序从前到后依次执行全部 $n$ 项操作，每项操作恰好执行一次。小 D 想知道，在所有操作执行完毕后，物资数量 $x$ 最大可能是多少？

从标准输入读入数据。 第一行包含一个正整数 $n$，表示操作的数量。 接下来 $n$ 行，第 $i$ 行包含两个正整数 $a_i, b_i$，描述第 $i$ 项操作的参数。

输出到标准输出。 输出一行一个整数，表示所有操作执行完毕后物资数量 $x$ 的最大可能值。

### 样例 1 解释 将第 $2$ 项操作移到序列末尾，操作执行顺序变为 $1, 3, 2$。每项操作执行完毕后，$x$ 的值依次变为 $1, 1, 90$。 若将第 $1$ 项移到末尾，最终 $x = 2$；若不调整顺序或将第 $3$ 项移到末尾，最终 $x = 1$。因此 $x$ 的最大可能值为 $90$。 ### 样例 2 见题目附件中的 `supply/supply2.in` 与 `supply/supply2.ans`。 该样例满足测试点 $1\sim4$ 的约束条件。 ### 样例 3 见题目附件中的 `supply/supply3.in` 与 `supply/supply3.ans`。 该样例满足测试点 $5\sim6$ 的约束条件。 ### 样例 4 见题目附件中的 `supply/supply4.in` 与 `supply/supply4.ans`。 该样例满足测试点 $7\sim10$ 的约束条件。 ### 数据范围与测试点 对于全部数据，保证 $1 \le n \le 2 \times 10^5$，$1 \le a_i, b_i \le 10^9$。请注意：**数据不保证 $a_i \le b_i$**。 本题共有 $10$ 个测试点，每个测试点 $10$ 分，各测试点独立计分。详细数据范围见下表。 | 测试点编号 | $n$ | 特殊性质 | 单点分值 | | --- | --- | --- | --- | | $1\sim4$ | $\le 2000$ | 无 | $10$ | | $5\sim6$ | $\le 2\times10^5$ | A | $10$ | | $7\sim10$ | $\le 2\times10^5$ | 无 | $10$ | 特殊性质 A：$b_1=b_2=\cdots=b_n$。