题目描述

本题使用文件输入输出：输入文件名为 meeting.in，输出文件名为 meeting.out。

公司有 $m$ 间一模一样的会议室。今天收到了 $n$ 个会议申请，第 $i$ 个会议从时刻 $l_i$ 开始、到时刻 $r_i$ 结束（$l_i < r_i$），会议期间要独占一间会议室。

同一间会议室里，前一场会议结束后下一场才能开始：如果前一场在时刻 $r$ 结束、后一场在时刻 $l$ 开始，要求 $r \le l$（结束时刻与开始时刻相同是允许的）。

你可以拒绝一些申请。请你安排会议室，使得被批准的会议数量最多，输出这个最大数量。

输入格式

输入文件名为 meeting.in。

第一行两个整数 $n, m$。

接下来 $n$ 行，每行两个整数 $l_i, r_i$。

输出格式

输出文件名为 meeting.out。

一行一个整数，表示最多能批准的会议数量。

样例 #1

样例输入 #1

5 2
1 4
2 5
3 6
4 7
5 8

样例输出 #1

4

样例解释

会议室 A 安排 $[1,4]$ 和 $[4,7]$，会议室 B 安排 $[2,5]$ 和 $[5,8]$，共 $4$ 场。

$5$ 场全批准是不行的：时刻 $3$ 到 $4$ 之间，$[1,4]$、$[2,5]$、$[3,6]$ 三场同时在开，而只有 $2$ 间会议室。

样例 #2

样例输入 #2

3 1
1 3
2 4
3 5

样例输出 #2

2

样例解释

只有一间会议室，选 $[1,3]$ 和 $[3,5]$。

样例输入 #3

见附件中的 meeting/meeting3.in。

样例输出 #3

见附件中的 meeting/meeting3.ans。

提示

数据范围

• 对于 $30\%$ 的数据：$n \le 15$；
• 对于 $60\%$ 的数据：$m = 1$；
• 对于 $100\%$ 的数据：$1 \le n \le 2 \times 10^5$，$1 \le m \le n$，$1 \le l_i < r_i \le 10^9$。

附件

• meeting3.in
• meeting3.ans