To Tell the Truth

Interview

Time limit2sMemory limit512 MB

Summary

Given n people each claiming the true count lies in [a,b], find the largest consistent truth-teller count or -1 if none exists.

Level: Medium6 of 10
Topics: Brute force, Math, Intervals
Solved: No attempts yet

Problem

There are n people in a room, each of whom always tells the truth or always lies. Each of them makes a statement of the form: "Some number between a and b (inclusive) of us are telling the truth." What is the maximum number of truth-tellers in the room?

Input

Each input consists of a single test case. Your program may be run multiple times on different inputs.

Each test case begins with a line containing an integer n (1 ≤ n ≤ 1,000), the number of people in the room.

Each of the next n lines contains two space-separated integers, a and b (0 ≤ a ≤ b ≤ n). Each line represents the statement of one person: "Some number between a and b (inclusive) of us are telling the truth."

Output

Output a single integer, the largest possible number of truth-tellers, or -1 if the statements are inconsistent.

Examples2

Example 1
Input
```
3
1 1
2 3
2 2
```
Expected output
```
2
```
Example 2
Input
```
8
0 1
1 7
4 8
3 7
1 2
4 5
3 7
1 8
```
Expected output
```
-1
```