题目描述

Ada、Bertrand 和 Charles 经常为看什么电视节目吵架。为了避免争吵，他们买了一台录像机。

这台录像机可以同时录制 $k$ 个不同的电视节目。每当某个录制槽中的节目结束时，该槽可以立刻开始录制另一个节目。

给定今天所有电视节目的开始和结束时间，以及录像机同时可录制的节目数 $k$。请计算一天中最多可以完整录制多少个节目。

注意，只有从开始到结束被完整录制的节目才计入答案。如果一个节目在时刻 $y_i$ 结束，另一个节目在同一时刻 $x_j=y_i$ 开始，它们可以使用同一个录制槽，不冲突。

输入格式

第一行包含两个整数 $n,k$：

• $1 \le k < n \le 100000$；
• $n$ 为电视节目数量；
• $k$ 为录像机可同时录制的节目数量。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 个节目从时刻 $x_i$ 开始，到时刻 $y_i$ 结束。

满足：

输出格式

输出一个整数，表示最多可以完整录制的节目数量。

输入输出样例 #1

输入 #1

3 1
1 2
2 3
2 3

输出 #1

2

输入输出样例 #2

输入 #2

4 1
1 3
4 6
7 8
2 5

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

3