4965 - 2023年第一届比赛第三题:安排社团

通过次数

1

提交次数

2

Time Limit : 1 秒
Memory Limit : 128 MB

最近学校里社团活动开展的非常好,但是专用教室太少了,有这样一个专用教室每个社团都想去开展活动,但是同一时间只能给一个社团使用,作为专用教室负责人的你,如何去尽可能多的安排社团来使用这个教室呢,每个社团的活动开始时间和结束时间不一样,有时会有重叠(社团进出教室不占任何时间)

Input

一个整数n为准备使用此专用教室的社团数 接下来n行,每行2个整数,分别为社团开始时间和结束时间

Output

一个整数,可以安排社团使用的数量

Examples

Input

5
8 10
12 14
9 15
17 19
11 13

Output

3

Hint

数据规模: 1<=n<=1000