310693: CF1872B. The Corridor or There and Back Again

B. The Corridor or There and Back Againtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are in a corridor that extends infinitely to the right, divided into square rooms. You start in room $1$, proceed to room $k$, and then return to room $1$. You can choose the value of $k$. Moving to an adjacent room takes $1$ second.

Additionally, there are $n$ traps in the corridor: the $i$-th trap is located in room $d_i$ and will be activated $s_i$ seconds after you enter the room $\boldsymbol{d_i}$. Once a trap is activated, you cannot enter or exit a room with that trap.

A schematic representation of a possible corridor and your path to room $k$ and back.

Determine the maximum value of $k$ that allows you to travel from room $1$ to room $k$ and then return to room $1$ safely.

For instance, if $n=1$ and $d_1=2, s_1=2$, you can proceed to room $k=2$ and return safely (the trap will activate at the moment $1+s_1=1+2=3$, it can't prevent you to return back). But if you attempt to reach room $k=3$, the trap will activate at the moment $1+s_1=1+2=3$, preventing your return (you would attempt to enter room $2$ on your way back at second $3$, but the activated trap would block you). Any larger value for $k$ is also not feasible. Thus, the answer is $k=2$.

Input

The first line of the input contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case description contains an integer $n$ ($1 \le n \le 100$) — the number of traps.

The following $n$ lines of each test case description present two integers $d_i$ and $s_i$ ($1 \le d_i, s_i \le 200$) — the parameters of a trap (you must leave room $d_i$ strictly before $s_i$ seconds have passed since entering this room). It's possible for multiple traps to occupy a single room (the values of $d_i$ can be repeated).

Output

For each test case, print the maximum value of $k$ that allows you to travel to room $k$ and return to room $1$ without encountering an active trap.

ExampleInput

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

Output

2
5
299
9
9
1
1

Note

The first test case is explained in the problem statement above.

In the second test case, the second trap prevents you from achieving $k\ge6$. If $k\ge6$, the second trap will activate at the moment $3+s_2=3+3=6$ (the time you enter room $4$ plus $s_2$). In the case of $k\ge6$, you will return to room $4$ at time $7$ or later. The trap will be active at that time. It can be shown that room $k=5$ can be reached without encountering an active trap.

In the third test case, you can make it to room $299$ and then immediately return to room $1$.

题目大意：
你在一个无限延伸的走廊里，从房间1出发，前往房间k，然后返回房间1。你可以选择k的值。移动到相邻的房间需要1秒。

此外，走廊里还有n个陷阱：第i个陷阱位于房间d_i，并且将在你进入房间d_i后的s_i秒被激活。一旦陷阱被激活，你就不能进入或离开有该陷阱的房间。

确定允许你从房间1安全地旅行到房间k然后返回房间1的最大k值。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
- 接下来是t个测试用例的描述。
- 每个测试用例的第一行包含一个整数n（1≤n≤100）——陷阱的数量。
- 接下来的n行，每行包含两个整数d_i和s_i（1≤d_i,s_i≤200）——一个陷阱的参数（你必须在这个房间停留少于s_i秒）。

输出：
- 对于每个测试用例，打印允许你旅行到房间k然后返回房间1而不遇到激活陷阱的最大k值。

示例：
输入：
```
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
```题目大意： 你在一个无限延伸的走廊里，从房间1出发，前往房间k，然后返回房间1。你可以选择k的值。移动到相邻的房间需要1秒。 此外，走廊里还有n个陷阱：第i个陷阱位于房间d_i，并且将在你进入房间d_i后的s_i秒被激活。一旦陷阱被激活，你就不能进入或离开有该陷阱的房间。 确定允许你从房间1安全地旅行到房间k然后返回房间1的最大k值。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 - 接下来是t个测试用例的描述。 - 每个测试用例的第一行包含一个整数n（1≤n≤100）——陷阱的数量。 - 接下来的n行，每行包含两个整数d_i和s_i（1≤d_i,s_i≤200）——一个陷阱的参数（你必须在这个房间停留少于s_i秒）。 输出： - 对于每个测试用例，打印允许你旅行到房间k然后返回房间1而不遇到激活陷阱的最大k值。 示例： 输入： ``` 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 ```