题目描述

你正在一个奇怪的地方探索：刚开始你位于 $1$ 号房间中。这个区域向右可以无限延伸，$1$ 号 房间的右边连接着 $2$ 号，$2$ 号房间的右边连接着 $3$ 号...

你希望是去到尽可能远的房间进行探索，再返回 $1$ 号房间，最后离开这个奇怪的地方。

不能去无限远的房间的原因是，这些房间里有 $n$ 个空间比较脆弱，当你经过 $d_i$ 个房间时，这个房间便进入崩溃的倒计时，将会在 $t_i$ 秒时崩溃。所以你在进 $d_i$ 后的 $t_i$ 秒及以后便不能回到 $d_i$ 房间了，需要在 $t_i-1$ 秒内返回。

你身手敏捷，在相邻两个房间移动的时间是 $1s$。现在请问你在这个奇怪的地方最远能够探索到几号房间？

输入格式

第一行一个正整数 $n$ 表示陷阱的数量。 接下来 $n$ 行，第 $i$ 行有两个正整数 $d_i$ 和 $t_i$ 表示第 $i$ 个脆弱的房间的位置和崩溃时间。

输出格式

输出一行一个正整数表示最远能到达哪个房间

输入输出样例

样例输入 # $1$

1
2 2

样例输出# $1$

2

样例解释 # $1$

如果仅去 $2$ 号房间，你将在 $1s$ 时进入 $2$ 号房间， $2s$ 时返回 $1$ 号房间，安全返回。 如果去了 $3$ 号房间，你将在 $1s$ 时进入 $2$ 号房间， $2s$ 时进入 $3$ 号房间。此时如果进入 $2$ 号房间， $3s$ 距离 $1s$ 已有 $2s$，$2$ 号房间已经崩溃，故无法返回。

样例 # $2$

样例输入 # $2$

3
5 8
3 179
100 1

样例输出 # $2$

8

样例解释 # $2$

若前往 $9$ 号房间，则返回 $5$ 号房间时，花费了$8s$，此时房间已经崩溃。故最远只能到达 $8$ 号房间，则返回 $5$ 号房间时只使用了 $6s$。

数据范围与约定

对于 $30\%$ 的数据，保证 $1 \leq n,d_i,t_i \leq 100$。

对于 $100\%$ 的数据，保证 $1\leq n,d_i,t_i \leq 10^6$ ，$d_i$ 互不相同。