Larry and Olympiads

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem types

Larry often goes to Olympiads to better his academic abilities. Unfortunately many of their classes overlap, and he can't take multiple classes at the same time.

There are N classes that Larry wants to take, each of which are offered on two separate days A and B. Larry cannot attend multiple classes on the same day.

Can Larry attend all N classes? If so, what is the earliest he can do so?

Input Specification

The first line contains an integer N\ (1 \leq N \leq 10^6).

The next N lines contain two integers A,B\ (1 \leq A < B \leq 10^9).

Output Specification

On one line you are to output the earliest day that Larry can have taken all the classes, or -1 if Larry is unable to take all the classes.

Sample Input

10 40
40 80
10 80

Sample Output



There are no comments at the moment.