学生 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 首先在第四天参加了第三科目的考试。然后他在第五天参加第二科目的考试。之后第六天,瓦莱拉参加第一门科目的考试。