題目描述

學校在最近幾天有n（n<=100）個活動，這些活動都需要使用學校的大禮堂，在同一時間，禮堂只能被一個活動使。由於有些活動時間上有衝突，學校辦公室人員只好讓一些活動放棄使用禮堂而使用其他教室。 現在給出n個活動使用禮堂的起始時間begin_i和結束時間end_i(begin_i < end_i)，請你幫助辦公室人員安排一些活動來使用禮堂，要求安排的活動盡量多。請問最多可以安排多少活動？ 請注意，開始時間和結束時間均指的是某個小時的0分0秒，如：3 5，指的是3:00~5:00，因此3 5和5 9這兩個時間段不算衝突的時間段。

輸入格式

第一行一個整數n(n<=100) _{接下來的n行，每行兩個整數，第一個begin_i，第二個是end_i(begin_i<} end_i <=32767)

輸出格式

輸出最多能安排的活動數

Samples

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

4

原始資料

• Zero1 題號：b016
• Hydro 題號：Z1016
• Locale：en_US
• Display：open