#A1002P1092. 探险

探险

题目描述

小博正在一个奇怪的地方探索:刚开始小博位于11号房间中。这个区域向右可以无限延伸,11号房间的右边连接着22号,22号房间的右边连接着33号...

小博希望去到尽可能远的房间进行探索,再返回11号房间,最后离开这个奇怪的地方。

不能去无限远的房间的原因是,这些房间里有nn个房间比较脆弱,当你经过did_i个房间时,这个房间便进入崩溃的倒计时,将会在tit_i秒时崩塌。所以小博在进入did_i后的tit_i秒及以后便不能回到did_i房间了,需要在ti1t_i-1秒内返回。

虽然小博身手敏捷,在相邻两个房间移动的时间只有1s1s,但是他也不想被崩塌的房间砸倒,现在请你帮他看看在这个奇怪的地方小博最远能够探索到几号房间?

输入格式

第一行一个正整数nn表示陷阱的数量。

接下来nn行,第ii行有两个正整数did_itit_i表示第ii个脆弱的房间的位置和崩塌时间。

输出格式

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

样例

1
2 2
2
3
5 8
3 179
100 1
8

数据范围

对于 30%30\% 的数据,保证1n,di,ti1001 \leq n,d_i,t_i \leq 100
对于 100%100\% 的数据,保证1n,di,ti1061\leq n,d_i,t_i \leq 10^6did_i互不相同。

样例解释

样例解释1

如果仅去22号房间,你将在1s1s时进入22号房间,2s2s时返回11号房间,安全返回

如果去了33号房间,你将在1s1s时进入22号房间,2s2s时进入33号房间。此时如果进入22号房间,3s3s距离1s1s已有2s2s22号房间已经崩溃,故无法返回。

样例解释2

若前往99号房间,则返回55号房间时,花费了8s8s,此时房间已经崩溃。故最远只能到达88号房间,则返回55号房间时只使用了6s6s