logo AlgoBeat OnlineJudge
登录 注册

#104425. [BZOJ 4425] [Nwerc2015]Assigning Workstations分配工作站

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

佩内洛普是新建立的超级计算机的管理员中的一员。 她的工作是分配工作站给到这里来运行他们的计算研究任务的研究人员。

佩内洛普非常懒惰,不喜欢为到达的研究者们解锁机器。 她可以从在她的办公桌远程解锁这些机器,但她并不觉得这卑贱的任务配得上她,所以她决定忽略安全指南偷偷懒。她可以直接地要求,研究者在他们离开时不用锁定自己的工作站,然后把未在使用且还在未锁定状态的工作站分配给新来的研究人员。 这样,她只需要为每一个工作站第一次被使用所属的研究员解锁工作站,这对佩内洛普的工作来说是一个巨大的改善。

不幸的是,如果一个工作站在未锁定且没被使用的状态下超过 分钟,会自动锁定自己,佩内洛普必须为使用它的下一个研究员再次打开它。 鉴于抵达和离开的研究人员的确切时间表,你可以告诉佩内洛普,要求研究者在离开时不锁定工作站最多可以使她节约多少次的解锁工作。你可以认为这儿总是有足够的可用工作站。

输入格式

一行两个整数 ,表示研究员的数量 以及工作站在未锁定且没被使用的状态下超过 分钟会自动锁定。

下面的 行,每一行两个整数 表示一个研究员在第 分钟时到达以及待了 分钟后离开。

输出格式

输出研究者在离开时不锁定工作站最多可以使她节约多少次解锁工作。

样例

样例输入 #1

3 5
1 5
6 3
14 6

样例输出 #1

2

样例输入 #2

5 10
2 6
1 2
17 7
3 9
15 6 

样例输出 #2

3

数据范围与提示

对于 的数据,