题目描述

有 $n$ 名同学申请使用自修教室，其中第 $i$ 名同学申请从第 $s_i$ 分钟开始使用，到第 $t_i$ 分钟结束时归还。若每间自修教室在同一时刻只能供一名同学使用，则为了满足所有同学的申请，至少需要多少间教室？

输入格式

第一行：单个正整数 $n$；

第二行到第 $n+1$ 行：第 $i+1$ 行有两个正整数 $s_i$ 与 $t_i$，表示一名同学申请教室的时间。

输出格式

单个正整数：表示至少需要多少间教室才能满足所有学生的申请。

样例

3
1 3
3 5
2 4

3

解释#1

三人各需要一间教室

3
1 10
20 30
40 50

1

数据范围

• 对于 $40\%$ 的数据，$1≤n≤1000$，$1≤s_i≤t_i≤10^3$；
• 对于 $70\%$ 的数据，$1≤n≤10^4$，$1≤s_i≤t_i≤10^5$；
• 对于 $100\%$ 的数据，$1≤n≤10^5$，$1≤s_i≤t_i≤10^7$；