#CF1907D. 线段间跳跃
线段间跳跃
CF1907D Jumping Through Segments
题目描述
Polycarp 正在为一个游戏设计关卡。这个关卡由数轴上的 个区间组成,第 个区间的起点为 ,终点为 。
玩家从坐标 处开始。在一次移动中,玩家可以移动到距离当前位置不超过 的任意点(坐标不必是整数)。在第 次移动后,玩家必须停在第 个区间内,即坐标 满足 。具体来说:
第一次移动后,玩家必须位于第一个区间( 到 )内;
第二次移动后,玩家必须位于第二个区间( 到 )内;
第 次移动后,玩家必须位于第 个区间( 到 )内。
如果玩家按照上述规则到达第 个区间,则视为完成关卡。Polycarp 发现,对于某些 的取值,关卡无法完成。
Polycarp 不希望关卡太简单,因此他希望你求出能够完成关卡的最小整数 。
输入格式
每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数,每组测试数据描述如下:
第一行输入一个整数 代表关卡中的区间数量。
此后 行,第 行输入两个整数 $l_i, r_i \left(0 \leqq l_i \leqq r_i \leqq 10^9\right)$ 代表第 个区间的左右端点。区间之间可能存在重叠。
除此之外,保证单个测试文件中所有测试数据的 之和不超过 。
输出格式
对于每一组测试数据,新起一行,输出一个整数,代表能够完成关卡的最小整数 。
测试样例
4
5
1 5
3 4
5 6
8 10
0 1
3
0 2
0 1
0 3
3
3 8
10 18
6 11
4
10 20
0 5
15 17
2 2
7
0
5
13
样例 3 解释
在第三组测试数据中,玩家可以按如下方式移动:
从 移动到 ();
从 移动到 ();
从 移动到 ()。
注意,最后一步玩家也可以选择不移动,依然可以完成关卡。