UOJ Logo

NOI.AC

1S 512MB

#757. a

Statistics

一道简单题。现在你有 $n$ 个任务需要完成,第 $i$ 个任务需要占据 $[l_i,r_i]$ 的时间,每个任务都会在瞬间结束,不会干扰到之后的任务。你不能太过分心,每一个瞬间至多能同时做 $k$ 个任务,请问最多能完成多少任务。

输入格式

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

接下来 $n$ 行 $l_i,r_i$。

输出格式

一行一个整数表示答案。

样例数据

输入样例一

3 1
1 2
2 3
1 3

输出样例一

2

数据规模与约定

对于 30% 的数据,$n \le 17$;

对于另外 30% 的数据,$k=1$;

对于 100% 的数据,$1\le k \le n\le 10^5,1\le l_i \le r_i \le n$。

时间限制:$1\text{s}$

空间限制:$512\text{MB}$