题目描述

在一个由 $N$ 行和 $10^9$ 列组成的方格城镇中，有 $N$ 堵墙，编号从 $1$ 到 $N$。
第 $i$ 堵墙从顶部开始的第 $i$ 行的左边第 $L_i$ 列到右边第 $R_i$ 列之间延伸。（参见样例输入和输出1中的图示）。

Takahashi 决定摧毁所有 $N$ 堵墙。
凭借他超人的力量，他一拳可以同时摧毁连续的 $D$ 列。

• 更正式地说，他可以选择一个介于 $1$ 和 $10^9 - D + 1$（含）之间的 整数 $x$ ，以此摧毁存在（或部分存在）于第 $x$ 列到第 $(x + D - 1)$ 列且尚未被摧毁的全部墙壁。

当一堵墙的一部分被摧毁时，整堵墙将会受到拳击的冲击而被完全摧毁。（参见样例输入和输出1中的图示）。

Takahashi 至少需要多少次拳击才能摧毁所有墙壁？

约束条件

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

输入

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

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

输出

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

示例输入1

3 3
1 2
4 7
5 9

示例输出1

2

下图描述了示例输入1中的墙壁布局。

他可以用两次拳击摧毁所有墙壁，例如如下所示。（下面，$[a, b]$ 表示从第 $a$ 列到第 $b$ 列的范围）

• 首先，拳击 $[2, 4]$。存在于范围 $[2, 4]$ 中的墙壁——墙壁1和墙壁2——受到损坏并被摧毁。
• 其次，拳击 $[5, 7]$。存在于范围 $[5, 7]$ 中的墙壁——墙壁3——受到损坏并被摧毁。

也可以按照以下方式用两次拳击摧毁所有墙壁：

• 首先，拳击 $[7, 9]$ 摧毁墙壁2和墙壁3。
• 其次，拳击 $[1, 3]$ 摧毁墙壁1。

示例输入2

3 3
1 2
4 7
4 9

示例输出2

1

与示例输入/输出1的区别在于，现在墙壁3覆盖范围是 $[4, 9]$，而不是 $[5, 9]$。
在这种情况下，他可以拳击 $[2, 4]$ 一拳即可摧毁全部墙壁。

示例输入3

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

示例输出3

3