A Way to Invite Friends

From tomorrow, the long-awaited summer vacation will begin. So I decided to invite my friends to go out to the sea.

However, many of my friends are shy. They would hate it if they knew that too many people would come with them.

Besides, many of my friends want to stand out. They will probably hate it if they know that not many people come with them.

Also, some of my friends are always shy, though they always want to stand out. They will surely hate if too many or too few people come with them.

This kind of thing should be more fun to do in large numbers. That's why I want to invite as many friends as possible. However, it is not good to force a friend you dislike.

How many friends can I invite up to?

I'm not very good at this kind of problem that seems to use my head. So I have a request for you. If you don't mind, could you solve this problem for me? No, I'm not overdoing it. But if I'm slacking off, I'm very happy.

Input

N a1 b1 a2 b2 .. .. .. aN bN

The integer N (1 ≤ N ≤ 100,000) is written on the first line of the input. This represents the number of friends.

On the following N lines, the integer ai and the integer bi (2 ≤ ai ≤ bi ≤ 100,001) are written separated by blanks. The integers ai and bi written on the 1 + i line indicate that the i-th friend does not want to go to the sea unless the number of people going to the sea is ai or more and bi or less. Note that the number of people going to the sea includes "I".

Output

Output the maximum number of friends you can invite to the sea so that no friends dislike it.

Examples

Input

4 2 5 4 7 2 4 3 6

Output

3

Input

5 8 100001 7 100001 12 100001 8 100001 3 100001

Output

0

Input

6 2 9 4 8 6 7 6 6 5 7 2 100001

Output

5

inputFormat

Input

N a1 b1 a2 b2 .. .. .. aN bN

The integer N (1 ≤ N ≤ 100,000) is written on the first line of the input. This represents the number of friends.

On the following N lines, the integer ai and the integer bi (2 ≤ ai ≤ bi ≤ 100,001) are written separated by blanks. The integers ai and bi written on the 1 + i line indicate that the i-th friend does not want to go to the sea unless the number of people going to the sea is ai or more and bi or less. Note that the number of people going to the sea includes "I".

outputFormat

Output

Output the maximum number of friends you can invite to the sea so that no friends dislike it.

Examples

Input

4 2 5 4 7 2 4 3 6

Output

3

Input

5 8 100001 7 100001 12 100001 8 100001 3 100001

Output

0

Input

6 2 9 4 8 6 7 6 6 5 7 2 100001

Output

5

样例

5
8 100001
7 100001
12 100001
8 100001
3 100001

0