← 返回题目列表

Codeforces · 479/C

C. 考试

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

学生 Valera 是该大学的本科生。他的期末考试即将来临,他将恰好通过 n 次考试。瓦莱拉是个聪明人,所以他第一次就能通过任何考试。此外,他可以在一天内参加几场考试,而且顺序不限。

根据日程安排,学生可以在第 ai 天参加第 i 科目的考试。不过,Valera 已与每位老师做了安排,第 i 科目的老师允许他在 bi (bi < ai) 日的安排时间之前参加考试。因此,Valera 可以在 ai 天或 bi 天参加第 i 个科目的考试。所有老师在实际考试当天将考试记录记入学生的记录簿中,并将分数日期记为数字ai。

Valera认为,如果记录簿中的条目不按照非递减日期的顺序排列,那会很奇怪。因此瓦莱拉请你帮助他。如果瓦莱拉参加考试,那么他可以参加期末考试的日期的最小可能值,使得他的记录簿中的所有记录都按照非递减日期的顺序排列。

输入

第一行包含一个正整数 n (1 ≤ n ≤ 5000) — Valera 将参加的考试次数。

接下来的 n 行中的每一行都包含两个空格分隔的正整数 ai 和 bi (1 ≤ bi < ai ≤ 109) — 相应地,考试表中的考试日期和通过第 i 次考试的最早日期。

输出

打印一个整数 - 如果 Valera 参加了所有考试,那么他可以参加最后一次考试的最小可能日期,以便他的记录簿中的所有记录都按照非递减日期的顺序排列。

示例

输入 #1

3
5 2
3 1
4 2

输出 #1

2

输入 #2

3
6 1
5 2
4 3

输出 #2

6

注意

在第一个示例中,Valera 首先在第一天参加第二科目的考试(老师记下安排日期为 3)。第二天,他参加第三门科目的考试(老师写下时间表日期 4),然后他参加第一门科目的考试(老师写下日期为 5 的分数)。因此,Valera 在第二天参加最后一次考试,日期将按非递减顺序排列:3、4、5。

在第二个示例中,Valera 首先在第四天参加了第三科目的考试。然后他在第五天参加第二科目的考试。之后第六天,瓦莱拉参加第一门科目的考试。