题目描述

强哥的城市被一群讨厌的墙挡住了去路！这个城市可以看作是一个超级宽的网格（有 $N$ 行，每行有 $10^9$ 列），每行都有一堵墙，第 $i$ 行的墙横跨第 $L_i$ 到 $R_i$ 列。

强哥决定用他的超级武器来拆除这些墙。每次攻击，他可以选定一个长度为 $D$ 的连续列区间（比如从 $x$ 到 $x+D-1$），然后所有和这个区间有重叠的墙都会被瞬间拆除（哪怕只重叠了一列也算）。

强哥想知道，最少需要多少次攻击才能把所有墙都拆光？

数据范围

• 墙的数量 $N$ 最多 $2 \times 10^5$ 堵。
• 每次攻击的宽度 $D$ 可以达到 $10^9$。
• 每堵墙的位置 $1 \leq L_i \leq R_i \leq 10^9$。
• 所有输入都是整数。

输入格式

输入按照以下格式给出：

N D
L1 R1
L2 R2
...
LN RN

输出格式

输出一个整数，表示强哥最少需要多少次攻击才能拆掉所有墙。

输入样例1

3 3
1 2
4 7
5 9

输出样例1

2

输入样例2

3 3
1 2
4 7
4 9

输出样例2

1

输入样例3

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

输出样例3

3