Problem C
Assigning Workstations

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
Input
The input consists of:
-
one line with two integers
( ), the number of researchers, and ( ), the number of minutes of inactivity after which a workstation locks itself; -
lines each with two integers and ( ), representing a researcher that arrives after minutes and stays for exactly minutes.
Output
Output the maximum number of unlockings Penelope may save herself.
Sample Input 1 | Sample Output 1 |
---|---|
3 5 1 5 6 3 14 6 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
5 10 2 6 1 2 17 7 3 9 15 6 |
3 |