题目描述

平行世界的宝可梦杰尼龟学会了一个新技能：飞叶快刀。在这个世界中，飞叶快刀具有范围伤害和穿透伤害，攻击力极强。可是，再强的杰尼龟也逃不了打工的命运，这次他接到的任务是 "拆墙"。

在一个 $n$ 行 $10^9$ 列的网格中有 $n$ 座墙，编号分别为 $1 \sim n$。其中，编号为 $i$ 的墙的左端点位于 $(i, l_i)$，右端点位于 $(i, r_i)$。

每使用一次 "飞叶快刀" 技能，杰尼龟可以打破 连续 的 $d$ 列里面的所有墙，也就是说，如果击中了第 $x$ 列，那么所有在第 $x$ 到第 $x+d-1$ 列里的墙都会被破坏。如果一座墙的一小部分被破坏了，整座墙就会倒塌。

但是打工实在太累了，杰尼龟想让你帮他算出它最少需要使用多少次 "飞叶快刀" 技能，才能让这 $n$ 座墙全都倒塌。

输入格式

第一行包含两个整数 $n$ 和 $d$ $(1 \leq n \leq 2 \times 10^5, 1 \leq d \leq 10^9)$。

接下来包含 $n$ 行，每行包含两个整数 $l_i, r_i$ $(1 \leq l_i \leq r_i \leq 10^9)$，分别代表第 $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

提示

对于样例 $1$，对应的墙壁分布如下图所示：

一种可行方案是：先攻击 $2 \sim 4$ 列，破坏墙壁 $1$ 和 $2$。然后攻击 $5 \sim 7$ 列，破坏墙壁 $3$。总共需要 $2$ 次。

方案不唯一。