免费WiFi
题号:NC14707
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

TRDD开了一家免费WiFi体验店, 所有人都可以免费连接WiFi, 只有一个条件, 你要提前一天预约。今天,TRDD收到了n(1 <= n <=1000)个人的预约, 每个人有一个时间段[L, R] (1 <= L <= R <= 5000)表示这个人预约连接WiFi从L时刻到R时刻。 但是市面上只有一种路由器, 这种路由器单台最多能同时连接m(n <= 100)台设备, TRDD想要知道最少使用多少台路由器就能保证明天每个人都能连上WiFi。

输入描述:

第一行包含两个数n(1 <= n <=1000), m (1 <= m <= 100)表示今天有n个人预约, 以及路由单台最大连接个数m。
之后有n行, 第i行有两个数字 [L, R] (1 <= L <= R <= 5000) 表示第i个人预约连接WiFi的时间是从L到R。

输出描述:

输出一个数字表示TRDD最少需要开启的路由器的个数。
示例1

输入

复制
4 1
1 5
2 7
3 4
6 9

输出

复制
3