Start: Jun, 21, 2017 00:00:00
2017暑期短学期题库(part 4)
End: Jul, 05, 2017 12:00:00
Time elapsed:
Time remaining:

【排序与查找】愚蠢的菜豚 2059

Time Limit:  1 s      Memory Limit:   128 MB
Submission:31     AC:14     Score:1

Description

菜豚挂了n门课,老师们安排好了他的补考时间,根据老师的安排,菜豚可以在第ai天参加第i场考试。但他知道补考并没有什么用,他想早点考完。老师每门课都给了他一个提前考的时间bi,因此他能在第ai天或bi天参加第i场考试(bi<ai),并且他可以一天考多门课。但是老师要求他的考试顺序必须是按照ai非递减的顺序考。

那么菜豚最少能在第几天能考完所有的考试呢?

Input

第一行输入一个整数n(0<n<10001)

接下来n行,每行有2个数字字:ai bi  (0<ai<10^9) (0<bi<10^9)

Output

输出答案

Samples

input
3 5 2 3 1 4 2
output
2

Hint

 如果样例为:

3

5 2

3 2

4 3

答案则为5, 根据ai的顺序 菜豚会在第2天考第二门,第3天考第三门,第5天考第一门。