题目描述

小 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$ 的最大可能值。

3
1 100
100 90
1 1

90

提示

样例 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$ 分，各测试点独立计分。详细数据范围见下表。

特殊性质 A：$b_1=b_2=\cdots=b_n$。