← 返回题目列表

Codeforces · 1907/D

D. 跳过段

中文机器翻译题面 查看原题

Polycarp 正在设计游戏的关卡。该级别由数轴上的 $$$n$$$ 段组成,其中第 $$$i$$$ 段从坐标 $$$l_i$$$ 的点开始,到坐标 $$$r_i$$$ 的点结束。

玩家从坐标为 $$$0$$$ 的点开始关卡。一次移动,他们可以移动到距离不超过 $$$k$$$ 内的任何点。在第 $$$i$$$ 次移动之后,玩家必须落在第 $$$i$$$ 段内,即在坐标 $$$x$$$ 处,使得 $$$l_i \le x \le r_i$$$。这意味着:

- 第一次移动后,它们必须位于第一个段内(从 $$$l_1$$$ 到 $$$r_1$$$);
- 第二次移动后,它们必须位于第二段内(从 $$$l_2$$$ 到 $$$r_2$$$);
- ...
- 在第 $$$n$$$ 次移动之后,它们必须位于第 $$$n$$$ 段内(从 $$$l_n$$$ 到 $$$r_n$$$)。

如果玩家按照上述规则到达第 $$$n$$$ 段,则认为该关卡已完成。经过一番思考,Polycarp 意识到用 $$$k$$$ 的某些值来完成关卡是不可能的。

Polycarp 不希望关卡太简单,因此他要求你确定可以完成关卡的最小整数 $$$k$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 关卡中的段数。

以下 $$$n$$$ 行。

第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) — 第 $$$i$$$ 段的边界。线段可能相交。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 可以完成关卡的 $$$k$$$ 的最小值。

示例

输入 #1

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

输出 #1

7
0
5
13

注意

在第三个示例中,玩家可以进行以下动作:

- 从点 $$$0$$$ 移动到点 $$$5$$$ ($$$3 \le 5 \le 8$$$);
- 从点 $$$5$$$ 移动到点 $$$10$$$ ($$$10 \le 10 \le 18$$$);
- 从点 $$$10$$$ 移动到点 $$$7$$$ ($$$6 \le 7 \le 11$$$)。

请注意,对于最后一步,玩家可以选择不移动并仍然完成关卡。