题目背景

剧院同一天收到了 n 场演出申请，第 i 场演出的表演时段是 [l_i, r_i]。可剧院这一天只搭得起 K 个舞台。

一场演出要么被接受、要么被拒绝；被接受的演出必须完整演完，同一舞台上的演出两两不冲突（一场演完、另一场紧接开演可以复用同一舞台，端点相接不算冲突）。

剧院想在这 K 个舞台上尽量多地安排演出。

题目描述

给定 n 场演出的时间段 [l_i, r_i] 和可用的舞台数量 K，从中选出尽可能多的演出，使得它们能被安排到 K 个舞台上且每个舞台上的演出两两不冲突。输出最多能安排的演出数量。

输入格式

第一行两个整数 n, K。

接下来 n 行，每行两个整数 l, r，表示一场演出的时间段。

输出格式

一个整数，表示最多能安排的演出数量。

输入输出样例

4 2
1 6
2 7
3 8
4 9

2

样例 1 解释

这 4 场演出在时刻 4 到 6 这一段里全都互相重叠，任意两场都冲突，只能各占一个舞台。2 个舞台最多同时安排 2 场，所以最多安排 2 场演出。

说明/提示

- 1 ≤ n ≤ 10^5 - 1 ≤ K ≤ n - 1 ≤ l < r ≤ 10^9 - 首尾相接的两场演出可以共用一个舞台