题目描述

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

输入格式

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

输出格式

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

3
1 3
3 5
2 4

3

3
1 10
20 30
40 50

1

提示

样例1解释：三人各需要一间教室。

数据范围

• 对于 40% 的数据，$1 \le n \le 15$；
• 对于 70% 的数据，$1 \le n \le 5\,000$；
• 对于 100% 的数据，$1 \le n \le 100\,000$；
• $1 \le s_i \le t_i \le 1\,000\,000$。