Recording the Moolympics

Interview

Time limit1sMemory limit128 MB

Summary

Select the largest set of programs that two tuners can record when one tuner cannot record overlapping programs.

Level: Medium5 of 10
Topics: Greedy, Sorting, Intervals
Solved: No attempts yet

Problem

Farmer John likes every cold-weather sport, and he likes the events with cows in them most of all. So he wants to record as much of this winter's Moolympics as he can.

The Moolympics broadcast schedule has $N$ programs, and every program has a fixed start time and end time. Farmer John's recorder has two tuners, so he can record two programs at the same time. A single tuner cannot record two programs whose times overlap, but it can go straight on to a program that starts at the exact moment the previous one ends.

Write a program that finds the largest number of programs Farmer John can record.

Input

The first line contains the number of programs $N$ ( $1 \le N \le 150$ ).

Each of the next $N$ lines contains the start time and the end time of one program, separated by a space. Both values are integers between $0$ and $10^9$ .

Output

Print the largest number of programs Farmer John can record.

Examples1

Example 1
Input
```
6
0 3
6 7
3 10
1 5
2 8
1 9
```
Expected output
```
4
```