Problem Description

Over the course of the year, as Mr Panda takes part in many activities such as projects and CCAs, his schedule is getting very packed. As the A-levels are coming near, he also needs to factor in a lot of homework and revision time into his schedule. Due to Mr Panda's lack of time management and addiction to the Binding of Isaac, he has been sleeping very late into the night and his panda eyes are getting from bad to worse! D:

His current schedule of N activities causes him to sleep very late and he needs to you to help him work out his daily schedule. Each activity i takes up a specific time period [Si,Ei] and once started must be carried out to completion. Given that Mr Panda can only carry out one activity at a time (he's a VERY BAD multitasker :P), help him find out what is the maximum the number of acitivites he can carry out in a single time period.


The first line contains a single integer N.

The next N lines contain two integers each separated by a space. The two integers on the (i+1)th line represents Si and Ei


The output should contain exactly one integer, the maximum number of activities that can be done in one time period.


Subtask 1(7%): 0 < N ≤ 20, 0 ≤ Si ≤ Ei ≤ 106

Subtask 2(17%): 0 < N ≤ 1000, 0 ≤ Si ≤ Ei ≤ 106

Subtask 3(27%): 0 < N ≤ 100000, 0 ≤ Si ≤ Ei ≤ 106

Subtask 4(49%): 0 < N ≤ 100000, 0 ≤ Si ≤ Ei ≤ 109

Subtask 5(0%): Sample

Sample Input

5 7
1 4
6 8
2 6
7 9

Sample Output


Explanation: Pick activities 1,2,5

Submitting .cpp to 'pandaeyes'

You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 512MB
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 7
2 17
3 27
4 49
5 0