题目描述

有 $10^9$ 个格子排成一行，从左到右编号从 $1$ 到 $10^9$。两个机器人正在格子里巡逻。每个机器人的最大速度是 $v$ 格每秒（$v$ 是整数），表示如果机器人目前在格子 $p$，它在下一秒可以移动到任意一个格子 $p'$，只要满足 $1 \le p' \le 10^9$ 且 $|p' - p| \le v$。

将有 $n$ 枚硬币在格子中出现。第 $i$ 枚硬币会在第 $t_i$ 秒出现在格子 $c_i$。如果有一个机器人同时也位于那个格子，它就会把硬币捡起来。否则硬币会马上消失。

更正式地，在每一秒内，以下事件会依次发生：

• 每个机器人可以移动到距离不超过 $v$ 的格子（也可以待在当前的格子里）。
• 硬币在格子中出现。
• 如果至少一个机器人和一枚硬币在同一个格子里，这枚硬币就会被收集。
• 所有未被收集的硬币消失。

您需要决定两个机器人在第 $1$ 秒开始前的初始位置，并合理地移动它们，使得所有硬币都能被收集，并且 $v$ 尽可能小。输出 $v$ 的最小值。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^6$）表示格子里将会出现的硬币数量。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $t_i$ 和 $c_i$（$1 \le t_i, c_i \le 10^9$）表示第 $i$ 枚硬币出现的时间以及第 $i$ 枚硬币出现的位置。保证对于所有 $1 \le i < n$ 有 $t_i \le t_{i + 1}$。同时保证对于所有 $i \ne j$ 有 $t_i \ne t_j$ 或 $c_i \ne c_j$。

保证所有数据 $n$ 之和不超过 $10^6$。

输出格式

每组数据输出一行一个整数，表示机器人最大速度的最小值。如果不可能收集所有硬币，输出 $\texttt{-1}$。

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

2
0
-1