题目描述

你处在一条无限向右延伸的走廊中，走廊被划分为若干方形房间。你从第 $1$ 号房间出发，前往第 $k$ 号房间，然后返回第 $1$ 号房间。你可以自行选择 $k$ 的值。每次移动到相邻的房间需要 $1$ 秒。

此外，走廊中有 $n$ 个陷阱：第 $i$ 个陷阱位于第 $d_i$ 号房间，并且会在你进入房间 $d_i$ 后 $s_i$ 秒激活。一旦陷阱被激活，你将无法进入或离开该房间。

上图是你前往第 $k$ 号房间并返回的路径示意图。请你确定能够安全往返的最大 $k$ 值。

例如，如果 $n=1$ 且 $d_1=2, s_1=2$，你可以安全地前往 $k=2$ 并返回（陷阱会在 $1+s_1=1+2=3$ 时刻激活，无法阻止你返回）。但如果你试图到达 $k=3$，陷阱会在 $1+s_1=1+2=3$ 时刻激活，阻止你返回（你将在第 $3$ 秒试图进入第 $2$ 号房间，但此时陷阱已激活并封锁了房间）。更大的 $k$ 也同样不可行。因此，答案为 $k=2$。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$），表示陷阱的数量。

接下来的 $n$ 行中，每行包含两个整数 $d_i$ 和 $s_i$（$1 \le d_i, s_i \le 200$），表示一个陷阱的参数（你必须在进入房间 $d_i$ 后严格少于 $s_i$ 秒离开该房间）。同一个房间可能有多个陷阱（$d_i$ 的值可能重复）。

输出格式

对于每个测试用例，输出一个整数，表示你能够安全往返的最大 $k$ 值。

说明/提示

第一个测试用例的解释见题目描述。

在第二个测试用例中，第二个陷阱阻止你取得 $k\ge6$。如果 $k\ge6$，第二个陷阱会在 $3+s_2=3+3=6$ 时刻激活（你进入第 $4$ 号房间的时刻加上 $s_2$）。在 $k\ge6$ 的情况下，你将在第 $7$ 秒或更晚返回第 $4$ 号房间。此时陷阱已激活。可以证明 $k=5$ 时可以安全往返。

在第三个测试用例中，你可以安全到达 $k=299$ 并立即返回第 $1$ 号房间。

由 ChatGPT 4.1 翻译

样例

7
1
2 2
3
2 8
4 3
5 2
1
200 200
4
1 20
5 9
3 179
100 1
2
10 1
1 18
2
1 1
1 2
3
1 3
1 1
1 3

2
5
299
9
9
1
1