问题描述

火焰车被派往前线攻打敌对阵营，敌方在一个可以看作是 $N$ 行、$10^9$ 列的战场上每一行都建造了一道防御壁垒，第 $i$ 个壁垒位于战场的第 $i$ 行，横跨从第 $L_i$ 列到第 $R_i$ 列的一段区域。

作为一位大魔导师，火焰车要释放强力法术摧毁敌方所有的防御壁垒。他每次可以释放出一道超级激光波，攻击连续的 $D$ 列格子。

具体来说，他可以选择一个起始列 $x$，使得从第 $x$ 列到第 $x + D - 1$ 列范围内的所有格子受到冲击。只要壁垒的任何部分受到攻击，这道壁垒就会被彻底摧毁。

请帮火焰车计算，至少需要释放多少次激光波才能摧毁敌方所有的防御壁垒？

输入格式

第一行包含两个整数 $N$ 和 $D$，分别表示敌方壁垒的数量和火焰车每次攻击所能覆盖的连续列数。

接下来 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$，表示第 $i$ 道防御壁垒所在行的范围是从第 $L_i$ 列到第 $R_i$ 列。

输出格式

输出一个整数，表示火焰车最少需要的释放次数，才能摧毁所有防御壁垒。

3 3
1 2
4 7
5 9

2

3 3
1 2
4 7
4 9

1

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

3

样例解释

对于第一个样例，火焰车可以这样攻击：

• 第一次超级激光波覆盖第 $2$ 到第 $4$ 列，摧毁了第 $1$ 道和第 $2$ 道壁垒。
• 第二次超级激光波覆盖第 $5$ 到第 $7$ 列，摧毁了第 $3$ 道壁垒。

或者先攻击第 $7$ 到第 $9$ 列，摧毁第 $2$ 和第 $3$ 道壁垒，再攻击第 $1$ 到第 $3$ 列，摧毁第 $1$ 道壁垒，也可以用两次完成。

在第二个样例中，因为第 $3$ 道壁垒的位置发生了变化，火焰车只需一次攻击覆盖第 $2$ 到第 $4$ 列，就能摧毁所有壁垒。

数据范围

对于 $20\%$ 的数据，保证 $D = 1$ 且 $L_i = R_i \le 10^5$。

对于 $40\%$ 的数据，保证 $D=1$ 且 $L_i = R_i \le 10^9$。

对于 $80\%$ 的数据，保证 $D=1$ 且 $L_i \le R_i \le10^9$。

对于 $100\%$ 的数据，保证 $1 \leq N \leq 2 \times 10^5$，$1 \leq D \leq 10^9$，$1 \leq L_i \leq R_i \leq 10^9$。