AT_abc230_d [ABC230D] Destroyer Takahashi

在一个被划分为 $N$ 行 $10^9$ 列格子的城市中，有 $N$ 面墙，每面墙都被分配了从 $1$ 到 $N$ 的编号。 第 $i$ 面墙位于第 $i$ 行，从左起第 $L_i$ 列到第 $R_i$ 列的范围内。（也请参考输入输出样例 $1$ 的图示。） 高桥君决定要摧毁所有 $N$ 面墙。 拥有超人力量的高桥君可以用一次拳击同时对连续的 $D$ 列造成伤害。 - 更严格地说，可以选择一个 $1$ 到 $10^9 - D + 1$ 之间的整数 $x$，对第 $x$ 列到第 $x + D - 1$ 列范围内（只要有一部分在该范围内）的所有尚未被摧毁的墙造成拳击伤害。 只要墙的任意部分受到伤害，整面墙就会因拳击的冲击波而被彻底摧毁。 （也请参考输入输出样例 $1$ 的说明。） 请问高桥君至少需要多少次拳击才能摧毁所有的墙？

输入以如下格式从标准输入读入。 > $N$ $D$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_N$ $R_N$

输出摧毁所有墙所需的最少拳击次数。

### 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq D \leq 10^9$ - $1 \leq L_i \leq R_i \leq 10^9$ - 所有输入均为整数。 ### 样例解释 1 下图展示了与输入样例 $1$ 对应的墙的分布。  例如，可以如下方式进行拳击，仅用 $2$ 次拳击摧毁所有的墙。（下述说明中，$a$ 列到 $b$ 列的范围记作 $[a, b]$。） - 首先，对 $[2, 4]$ 进行拳击。位于 $[2, 4]$ 的墙 $1$ 和墙 $2$ 受到伤害，被摧毁。 - 然后对 $[5, 7]$ 进行拳击。位于 $[5, 7]$ 的墙 $3$ 受到伤害，被摧毁。 另外，也可以如下方式用 $2$ 次拳击摧毁所有墙： - 首先对 $[7, 9]$ 进行拳击，摧毁墙 $2$ 和墙 $3$。 - 然后对 $[1, 3]$ 进行拳击，摧毁墙 $1$。 ### 样例解释 2 与输入输出样例 $1$ 相比，墙 $3$ 的范围从 $[5, 9]$ 变成了 $[4, 9]$。 在这种情况下，只需对 $[2, 4]$ 进行一次拳击即可摧毁所有的墙。 由 ChatGPT 4.1 翻译