time limit per test
2 seconds
memory limit per test
256 megabytes
You are in a corridor that extends infinitely to the right, divided into square rooms. You start in room 11, proceed to room kk, and then return to room 11. You can choose the value of kk. Moving to an adjacent room takes 11 second.
Additionally, there are nn traps in the corridor: the ii-th trap is located in room didi and will be activated sisi seconds after you enter the room didi. 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 kk and back.
Determine the maximum value of kk that allows you to travel from room 11 to room kk and then return to room 11 safely.
For instance, if n=1n=1 and d1=2,s1=2d1=2,s1=2, you can proceed to room k=2k=2 and return safely (the trap will activate at the moment 1+s1=1+2=31+s1=1+2=3, it can't prevent you to return back). But if you attempt to reach room k=3k=3, the trap will activate at the moment 1+s1=1+2=31+s1=1+2=3, preventing your return (you would attempt to enter room 22 on your way back at second 33, but the activated trap would block you). Any larger value for kk is also not feasible. Thus, the answer is k=2k=2.
Input
The first line of the input contains an integer tt (1≤t≤10001≤t≤1000) — the number of test cases.
The descriptions of the test cases follow.
The first line of each test case description contains an integer nn (1≤n≤1001≤n≤100) — the number of traps.
The following nn lines of each test case description present two integers didi and sisi (1≤di,si≤2001≤di,si≤200) — the parameters of a trap (you must leave room didi strictly before sisi seconds have passed since entering this room). It's possible for multiple traps to occupy a single room (the values of didi can be repeated).
Output
For each test case, print the maximum value of kk that allows you to travel to room kk and return to room 11 without encountering an active trap.
Example
Input
Copy
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
Copy
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≥6k≥6. If k≥6k≥6, the second trap will activate at the moment 3+s2=3+3=63+s2=3+3=6 (the time you enter room 44 plus s2s2). In the case of k≥6k≥6, you will return to room 44 at time 77 or later. The trap will be active at that time. It can be shown that room k=5k=5 can be reached without encountering an active trap.
In the third test case, you can make it to room 299299 and then immediately return to room 11.
解题说明：此题是一道模拟题，根据题目意思，陷阱触发的时间为第一次进入到这个房间的时间加上触发的时间，即如果第二个房间存在一个陷阱，触发的时间为2秒，那么这个陷阱将在1+2=3秒时起作用，我们要安全的回到初始的位置，问我们最远能走到多远的房间。可以直接遍历所有陷阱触发情况下最远能走到的房间，然后找出最小值即可。
#include<stdio.h>
int main()
{int t;scanf("%d", &t);while (t--) {int n, temp = 10000000;scanf("%d", &n);while (n--){int a, b, flag;scanf("%d%d", &a, &b);b = b - 1;flag = a + (b / 2);if (flag < temp) {temp = flag;}}printf("%d\n", temp);}return 0;
}
