CF1872B.The Corridor or There and Back Again

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$ .

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).

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.

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$ .