← 返回题目列表

Codeforces · 1879/A

A. 被操纵!

中文机器翻译题面 查看原题

Monocarp 组织举重比赛。有$$$n$$$名运动员参加比赛,第$$$i$$$名运动员的力量为$$$s_i$$$,耐力为$$$e_i$$$。 $$$1$$$-st 运动员是 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($$$1$$$-st 运动员)赢得比赛。帮助他选择 $$$w$$$ 的值,否则报告不可能。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 运动员的数量。然后是 $$$n$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$s_i$$$ 和 $$$e_i$$$ ($$$1 \le s_i \le 10^9$$$; $$$1 \le e_i \le 100$$$) — 第 $$$i$$$ 运动员的力量和耐力。

输出

对于每个测试用例,打印答案如下:

- 如果答案存在,则打印一个整数 - $$$w$$$ 满足约束的值。您打印的整数应满足 $$$1 \le w \le 10^9$$$。可以证明,如果答案存在,则 $$$w$$$ 也至少存在一个这样的值。如果有多个答案,可以打印其中任意一个;
- 否则,打印一个整数 $$$-1$$$。

示例

输入 #1

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

输出 #1

5
-1
-1

注意

示例的第一个测试用例在语句中进行了描述。