CodePSU 2018 - Advanced

Start

2018-03-18 18:00 UTC

CodePSU 2018 - Advanced

End

2018-03-18 22:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -271 days 8:45:59

Time elapsed

4:00:00

Time remaining

0:00:00

Problem D
Office Hour Visits

You are taking a very full course load this semester and have to visit your TAs’ office hours. All of them have their office hours at different times during the week! You want to try to visit as many of your TAs as possible given the times that their office hours occur. Luckily all of their office hours are in the same building so it takes you no time to travel from one to another. Of course, you don’t need to sleep, eat or do anything normal humans do because that would ruin the purpose of this problem!

Note: if you choose attend a TA’s office hours, you must attend for the whole time, because you are very behind in the class and you need a LOT of help.

Input

The first line consists of the number of TAs,$N$ ($2 < N < 50,000$), that you can visit. Then, the next $N$ lines each consist of the time that the TA’s office hours start, $T_ s$, and the time they end, $T_ e$, order ($0 \leq T_ s < T_ e \leq 10,080$). The times are given as the number of minutes into the week (i.e. 0 would be midnight and 60 would be 1 AM).

Output

Print out the maximum number of TAs that you can visit this week, given that if you choose to visit a TA, you have to stay for the entire duration of their office hours.

Sample Input 1 Sample Output 1
5
1 3
2 5
3 7
4 5
5 8
3