题目描述

设有 n 个会议 E = {1,2,…,n} 要使用同一资源,同一时间内只允许一个会议使用该资源。 设会议 i 的起止时间区间 $[si, fi)$ ,如果选择了会议 i ,则它在时间区间 $[si, fi)$ 内占用该资源;若 $[si, fi)$ 与 $[sj, fj)$ 不相交 , 则称会议 i 与 j 是相容的 。求解目标是在所给的会议集合中选出最大相容会议子集。

本题以会议次数为主，不分大会议和小会议室

输入格式

第 1 行为一个整数 n ( n $\leq$ 10000 ) ，表示申请的数目；

以下 n 行每行包含两个整数 p，k ( 1 $\leq$ p < k $\leq$ 30000 )，表示这个申请的起始时间和终止时间。

输出格式

一个整数，表示大厅最大可使用的次数。

样例

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

4

5
1 1000
2 9999
1000 9999
10000 20000
20000 30000

4