무림픽 녹화하기

면접 대비

시간 제한1초메모리 제한128 MB

요약

겹치는 시간대 프로그램을 한 녹화기가 동시에 담지 못할 때 두 대의 녹화기로 녹화하는 프로그램 수를 가장 크게 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 구간
정답자: 아직 제출이 없습니다

문제

존은 추운 날씨에 하는 운동 경기를 좋아하고, 그중에서도 소가 출전하는 종목을 가장 좋아한다. 그래서 이번 겨울에 열리는 무림픽 중계를 최대한 많이 녹화하려고 한다.

무림픽 중계 편성표에는 프로그램이 $N$ 개 있고, 프로그램마다 시작 시각과 종료 시각이 정해져 있다. 존의 녹화기에는 튜너가 두 개 달려 있어서 프로그램 두 개를 동시에 녹화할 수 있다. 한 튜너로 시간이 겹치는 두 프로그램을 녹화하지는 못하지만, 앞 프로그램이 끝나는 시각에 시작하는 프로그램은 같은 튜너로 이어서 녹화할 수 있다.

존이 녹화할 수 있는 프로그램 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 프로그램의 수 $N$ 이 주어진다. ( $1 \le N \le 150$ )

다음 $N$ 개 줄에는 각 줄마다 프로그램 하나의 시작 시각과 종료 시각이 빈 칸을 사이에 두고 주어진다. 두 값 모두 $0$ 이상 $10^9$ 이하의 정수다.

출력

첫째 줄에 존이 녹화할 수 있는 프로그램 수의 최댓값을 출력한다.

예제1

예제 1
입력
```
6
0 3
6 7
3 10
1 5
2 8
1 9
```
예상 출력
```
4
```