分配工作站(Assigning Workstations)

题目描述

本题对应 NWERC 2015 Problem A：Assigning Workstations。

研究所里有 $n$ 名研究员需要使用工作站。第 $i$ 名研究员会在时刻 $a_i$ 到达，并持续使用工作站 $s_i$ 个单位时间（即在时刻 $a_i + s_i$ 离开）。

为了信息安全，每台工作站在无人使用时默认处于锁定状态；当一名研究员开始使用处于锁定状态的工作站时，管理员 Penelope 必须亲自为其解锁一次。

为了减轻负担，工作站设有自动休眠锁定机制：当一名研究员在时刻 $t$ 离开某台工作站后，该工作站在接下来的 $m$ 个单位时间内（即区间 $[t, t + m]$ 内）保持未锁定状态。如果在时刻 $t + m$ 或更早有另一名研究员接替使用这台工作站，则无需重新解锁；一旦超过时刻 $t + m$ 仍无人使用，工作站将自动重新锁定。

假设工作站数量充足，请你合理安排每位研究员使用的工作站，使得管理员 Penelope 能够省去尽可能多次解锁操作，并输出最多可以省去的解锁次数。

输入格式

第一行包含两个正整数 $n, m$，分别表示研究员人数与工作站未锁定保持时间。

接下来 $n$ 行，每行包含两个正整数 $a_i, s_i$，分别表示第 $i$ 名研究员到达的时刻与使用时长。

输出格式

输出一行一个整数，表示管理员最多可以省去的解锁次数。

样例输入 #1

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

样例输出 #1

3

样例输入 #2

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

样例输出 #2

1

数据范围

对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^5$，$1 \le m \le 10^8$，$1 \le a_i, s_i \le 10^8$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接