#A1002P1092. 探险
探险
题目描述
小博正在一个奇怪的地方探索:刚开始小博位于号房间中。这个区域向右可以无限延伸,号房间的右边连接着号,号房间的右边连接着号...
小博希望去到尽可能远的房间进行探索,再返回号房间,最后离开这个奇怪的地方。
不能去无限远的房间的原因是,这些房间里有个房间比较脆弱,当你经过个房间时,这个房间便进入崩溃的倒计时,将会在秒时崩塌。所以小博在进入后的秒及以后便不能回到房间了,需要在秒内返回。
虽然小博身手敏捷,在相邻两个房间移动的时间只有,但是他也不想被崩塌的房间砸倒,现在请你帮他看看在这个奇怪的地方小博最远能够探索到几号房间?
输入格式
第一行一个正整数表示陷阱的数量。
接下来行,第行有两个正整数和表示第个脆弱的房间的位置和崩塌时间。
输出格式
输出一行一个正整数,表示小博最远能到达哪个房间。
样例
1
2 2
2
3
5 8
3 179
100 1
8
数据范围
对于 的数据,保证。
对于 的数据,保证,互不相同。
样例解释
样例解释1
如果仅去号房间,你将在时进入号房间,时返回号房间,安全返回
如果去了号房间,你将在时进入号房间,时进入号房间。此时如果进入号房间,距离已有,号房间已经崩溃,故无法返回。
样例解释2
若前往号房间,则返回号房间时,花费了,此时房间已经崩溃。故最远只能到达号房间,则返回号房间时只使用了。