题目描述

在一个 $N$ 行 $10^9$ 列的网格中有 $N$ 面墙，编号为 $1$ 到 $N$。其中，编号为 $i$ 的墙的左端点位于 $(i,L_i)$ ——即第 $i$ 行第 $L_i$ 列，右端点位于 $(i,R_i)$。

你的拳头一次可以打破 连续 的 $D$ 列里面的所有墙，也就是说，如果你用拳头击中了第 $x$ 列，那么所有 一部分在第 $x$ 到第 $x+D-1$ 列里的墙 会被破坏。如果一座墙的一小部分被破坏了，整座墙就会倒塌。问题是，最少你需要打几拳才能让 $N$ 座墙全都倒塌？

输入格式

第一行输入 $N,D$

接下来 $N$ 行每行两个整数 $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

提示

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ D\ \leq\ 10^9$
• $1\ \leq\ L_i\ \leq\ R_i\ \leq\ 10^9$