310742: CF1879A. Rigged!

A. Rigged!time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Monocarp organizes a weightlifting competition. There are $n$ athletes participating in the competition, the $i$-th athlete has strength $s_i$ and endurance $e_i$. The $1$-st athlete is Monocarp's friend Polycarp, and Monocarp really wants Polycarp to win.

The competition will be conducted as follows. The jury will choose a positive (greater than zero) integer $w$, which denotes the weight of the barbell that will be used in the competition. The goal for each athlete is to lift the barbell as many times as possible. The athlete who lifts the barbell the most amount of times will be declared the winner (if there are multiple such athletes — there's no winner).

If the barbell's weight $w$ is strictly greater than the strength of the $i$-th athlete $s_i$, then the $i$-th athlete will be unable to lift the barbell even one single time. Otherwise, the $i$-th athlete will be able to lift the barbell, and the number of times he does it will be equal to his endurance $e_i$.

For example, suppose there are $4$ athletes with parameters $s_1 = 7, e_1 = 4$; $s_2 = 9, e_2 = 3$; $s_3 = 4, e_3 = 6$; $s_4 = 2, e_4 = 2$. If the weight of the barbell is $5$, then:

• the first athlete will be able to lift the barbell $4$ times;
• the second athlete will be able to lift the barbell $3$ times;
• the third athlete will be unable to lift the barbell;
• the fourth athlete will be unable to lift the barbell.

Monocarp wants to choose $w$ in such a way that Polycarp (the $1$-st athlete) wins the competition. Help him to choose the value of $w$, or report that it is impossible.

Input

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains one integer $n$ ($2 \le n \le 100$) — the number of athletes. Then $n$ lines follow, the $i$-th of them contains two integers $s_i$ and $e_i$ ($1 \le s_i \le 10^9$; $1 \le e_i \le 100$) — the strength and the endurance of the $i$-th athlete.

Output

For each test case, print the answer as follows:

• if the answer exists, print one integer — the value of $w$ meeting the constraints. The integer you print should satisfy $1 \le w \le 10^9$. It can be shown that if the answer exists, at least one such value of $w$ exists as well. If there are multiple answers, you can print any of them;
• otherwise, print one integer $-1$.

ExampleInput

3
4
7 4
9 3
4 6
2 2
2
4 6
100 100
2
1337 3
1337 3

Output

5
-1
-1

Note

The first test case of the example is described in the statement.

题目大意：
Monocarp组织了一场举重比赛。共有n名运动员参加比赛，第i名运动员的力量为s_i，耐力为e_i。第一名运动员是Monocarp的朋友Polycarp，Monocarp非常希望Polycarp赢得比赛。

比赛将按以下方式进行。裁判将选择一个正整数w（大于零），表示比赛中将使用的哑铃的重量。每个运动员的目标是尽可能多次举起哑铃。举起哑铃次数最多的运动员将被宣布为获胜者（如果有多个这样的运动员，则没有获胜者）。

如果哑铃的重量w严格大于第i名运动员的力量s_i，那么第i名运动员将无法举起哑铃，即使一次也不行。否则，第i名运动员将能够举起哑铃，他举起的次数将等于他的耐力e_i。

例如，假设有4名运动员，参数为s_1 = 7, e_1 = 4; s_2 = 9, e_2 = 3; s_3 = 4, e_3 = 6; s_4 = 2, e_4 = 2。如果哑铃的重量为5，那么：
- 第一名运动员将能够举起哑铃4次；
- 第二名运动员将能够举起哑铃3次；
- 第三名运动员将无法举起哑铃；
- 第四名运动员将无法举起哑铃。

Monocarp希望选择w，使得Polycarp（第一名运动员）赢得比赛。帮助他选择w的值，或者报告这是不可能的。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤100）——测试用例的数量。
每个测试用例的第一行包含一个整数n（2≤n≤100）——运动员的数量。然后是n行，每行包含两个整数s_i和e_i（1≤s_i≤10^9；1≤e_i≤100）——第i个运动员的力量和耐力。

输出：
对于每个测试用例，按以下格式打印答案：
- 如果答案存在，打印一个整数——满足约束条件的w的值。你打印的整数应该满足1≤w≤10^9。可以证明，如果答案存在，至少存在一个这样的w值。如果有多个答案，你可以打印其中任何一个；
- 否则，打印一个整数-1。题目大意： Monocarp组织了一场举重比赛。共有n名运动员参加比赛，第i名运动员的力量为s_i，耐力为e_i。第一名运动员是Monocarp的朋友Polycarp，Monocarp非常希望Polycarp赢得比赛。 比赛将按以下方式进行。裁判将选择一个正整数w（大于零），表示比赛中将使用的哑铃的重量。每个运动员的目标是尽可能多次举起哑铃。举起哑铃次数最多的运动员将被宣布为获胜者（如果有多个这样的运动员，则没有获胜者）。 如果哑铃的重量w严格大于第i名运动员的力量s_i，那么第i名运动员将无法举起哑铃，即使一次也不行。否则，第i名运动员将能够举起哑铃，他举起的次数将等于他的耐力e_i。 例如，假设有4名运动员，参数为s_1 = 7, e_1 = 4; s_2 = 9, e_2 = 3; s_3 = 4, e_3 = 6; s_4 = 2, e_4 = 2。如果哑铃的重量为5，那么： - 第一名运动员将能够举起哑铃4次； - 第二名运动员将能够举起哑铃3次； - 第三名运动员将无法举起哑铃； - 第四名运动员将无法举起哑铃。 Monocarp希望选择w，使得Polycarp（第一名运动员）赢得比赛。帮助他选择w的值，或者报告这是不可能的。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤100）——测试用例的数量。 每个测试用例的第一行包含一个整数n（2≤n≤100）——运动员的数量。然后是n行，每行包含两个整数s_i和e_i（1≤s_i≤10^9；1≤e_i≤100）——第i个运动员的力量和耐力。 输出： 对于每个测试用例，按以下格式打印答案： - 如果答案存在，打印一个整数——满足约束条件的w的值。你打印的整数应该满足1≤w≤10^9。可以证明，如果答案存在，至少存在一个这样的w值。如果有多个答案，你可以打印其中任何一个； - 否则，打印一个整数-1。