摧毁墙壁

题目描述

在一个被划分为 $N$ 行、$10^9$ 列的网格小镇上，有 $N$ 堵墙，编号为 $1$ 到 $N$。

墙 $i$ 位于从上数第 $i$ 行，覆盖从左数第 $L_i$ 列到第 $R_i$ 列。

高桥决定摧毁全部 $N$ 堵墙。

凭借超人力气，他的一拳可以同时破坏连续的 $D$ 列。

更确切地说，他可以选择一个介于 $1$ 到 $10^9 - D + 1$（含端点）之间的整数 $x$，破坏所有存在于第 $x$ 列到第 $(x + D - 1)$ 列、且尚未被破坏的墙（部分存在于这些列中即可）。

当墙的一部分受到破坏时，整堵墙都会因这一拳的冲击而被摧毁。

要摧毁所有墙，高桥最少需要出拳多少次？

输入格式

输入按以下格式从标准输入给出：

$N$ $D$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

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

样例

3 3
1 2
4 7
5 9

2

下面用 $\lbrack a, b \rbrack$ 表示从第 $a$ 列到第 $b$ 列的范围。他可以用两次出拳摧毁所有墙，例如：

先出拳 $\lbrack 2, 4 \rbrack$。存在于 $\lbrack 2, 4 \rbrack$ 中的墙——墙 1 和墙 2——受到破坏并被摧毁。

再出拳 $\lbrack 5, 7 \rbrack$。存在于 $\lbrack 5, 7 \rbrack$ 中的墙——墙 3——受到破坏并被摧毁。

也可以这样用两次出拳摧毁所有墙：

先出拳 $\lbrack 7, 9 \rbrack$ 摧毁墙 2 和墙 3。

再出拳 $\lbrack 1, 3 \rbrack$ 摧毁墙 1。

3 3
1 2
4 7
4 9

1

与样例输入输出 1 的不同之处在于，墙 3 现在覆盖 $\lbrack 4, 9 \rbrack$，而不是 $\lbrack 5, 9 \rbrack$。

这种情况下，他可以出拳 $\lbrack 2, 4 \rbrack$，用一拳摧毁所有墙。

5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000

3

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq D \leq 10^9$
• $1 \leq L_i \leq R_i \leq 10^9$
• 输入中的所有值均为整数。