8425: BZOJ4425：[Nwerc2015]Assigning Workstations分配工作站

Penelope is part of the admin team of the newly built supercomputer. Her job is to assign workstations to the researchers who come here to run their computations at the supercomputer. Penelope is very lazy and hates unlocking machines for the arriving researchers. She can unlock the machines remotely from her desk, but does not feel that this menial task matches her qualifications. Should she decide to ignore the security guidelines she could simply ask the researchers not to lock their workstations when they leave, and then assign new researchers to workstations that are not used any more but that are still unlocked. That way, she only needs to unlock each workstation for the first researcher using it, which would be a huge improvement for Penelope. Unfortunately, unused workstations lock themselves automatically if they are unused for more than mm minutes. After a workstation has locked itself, Penelope has to unlock it again for the next researcher using it. Given the exact schedule of arriving and leaving researchers, can you tell Penelope how many unlockings she may save by asking the researchers not to lock their workstations when they leave and assigning arriving researchers to workstations in an optimal way? You may assume that there are always enough workstations available. Input The input consists of: one line with two integers n (1≤n≤300000), the number of researchers, and m (1≤m≤10^8), the number of minutes of inactivity after which a workstation locks itself; n lines each with two integers a and s (1≤a,s≤10^8), representing a researcher that arrives after a minutes and stays for exactly s minutes. Output Output the maximum number of unlockings Penelope may save herself. 佩内洛普是新建立的超级计算机的管理员中的一员。 她的工作是分配工作站给到这里来运行他们的计算研究任务的研究人员。 佩内洛普非常懒惰，不喜欢为到达的研究者们解锁机器。 她可以从在她的办公桌远程解锁这些机器，但她并不觉得这卑贱的任务配得上她，所以她决定忽略安全指南偷偷懒。她可以直接地要求，研究者在他们离开时不用锁定自己的工作站，然后把未在使用且还在未锁定状态的工作站分配给新来的研究人员。 这样，她只需要为每一个工作站第一次被使用所属的研究员解锁工作站，这对佩内洛普的工作来说是一个巨大的改善。 不幸的是，如果一个工作站在未锁定且没被使用的状态下超过m分钟，会自动锁定自己，佩内洛普必须为使用它的下一个研究员再次打开它。 鉴于抵达和离开的研究人员的确切时间表，你可以告诉佩内洛普，要求研究者在离开时不锁定工作站最多可以使她节约多少次的解锁工作。你可以认为这儿总是有足够的可用工作站。

输入格式

一行两个整数n (1≤n≤300000) 研究员的数量n，以及 m (1≤m≤100000000) 工作站在未锁定且没被使用的状态下超过m分钟会自动锁定。 下面的n行，每一行两个整数a与s (1≤a,s≤100000000) 表示一个研究员在第a分钟时到达以及待了s分钟后离开。

输出格式

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

样例输入

Sample Input 1
3 5
1 5
6 3
14 6 
Sample Input 2
5 10
2 6
1 2
17 7
3 9
15 6 

样例输出

Sample Output 1
2

Sample Output 2
3

提示

没有写明提示

题目来源

没有写明来源