Activity Selection

Problem Background

Special for beginners, ^_^

Problem Description

The school has $n\;(n\le 1000)$ activities in the next few days, all of which need to use the school auditorium. At any given time, the auditorium can only be used by one activity. Because some activities overlap in time, the school office has to let some activities give up the auditorium and use other classrooms instead.

Given the start time $begin_i$ and end time $end_i\;(begin_i \le end_i)$ of each of the $n$ activities' use of the auditorium, help the office arrange as many activities as possible to use the auditorium.

What is the maximum number of activities that can be scheduled?

Note that the start time and end time both refer to the 0th minute and 0th second of some hour. For example, 3 5 means 3:00–5:00, so the time intervals 3 5 and 5 9 do not conflict.

Input Format

The first line is an integer $n\;(n\le 1000)$.

The following $n$ lines each contain two integers: the first is $begin_i$, the second is $end_i\;(begin_i < end_i \le 32767)$.

Output Format

Output the maximum number of activities that can be scheduled.

Sample Input

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

Sample Output

4

Constraints

1s, 1024KiB for each test case.