← 返回题目列表

Codeforces · 1027/F

F. BSU 会议

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

Polycarp 在 Berland 州立大学学习。很快他就要参加考试了。他必须准确地通过 $$$n$$$ 考试。

对于每项考试 $$$i$$$,已知有两天: $$$a_i$$$ — 第一次有机会通过考试的日期,$$$b_i$$$ — 第二次有机会通过考试的日期 ($$$a_i < b_i$$$)。波利卡普每天最多可以通过一场考试。对于每次考试,波利卡普都会自行选择通过考试的日期。他必须通过所有 $$$n$$$ 考试。

坡旅甲希望尽快通过所有考试。打印 Polycarp 可以通过所有 $$$n$$$ 考试的最小日期索引,或者如果他根本无法通过所有考试,则打印 -1。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 考试数量。

接下来的 $$$n$$$ 行每行包含两个整数:$$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i < b_i \le 10^9$$$),其中 $$$a_i$$$ 是第一个通过第 $$$i$$$ 考试的天数,$$$b_i$$$ 是天数第二次通过第 $$$i$$$ 考试的时间。

输出

如果 Polycarp 无法通过所有 $$$n$$$ 考试,则打印 -1。否则打印 Polycarp 可以做到这一点的最小日期索引。

示例

输入 #1

2
1 5
1 7

输出 #1

5

输入 #2

3
5 13
1 5
1 7

输出 #2

7

输入 #3

3
10 40
40 80
10 80

输出 #3

80

输入#4

3
99 100
99 100
99 100

输出#4

-1