题目描述

$N$ 行 $10^9$ 列の格子状の区画に区切られた街に $N$ 枚の壁があり、$1$ から $N$ までの番号が割り振られています。
壁 $i$ は上から $i$ 行目、左から $L_i$ 列目から $R_i$ 列目の範囲にあります。(入出力例 $1$ の図も参考にしてください。)

高橋君は $N$ 枚の壁をすべて破壊することにしました。
超人的な腕力を持つ高橋君は、$1$ 回のパンチで連続する $D$ 列にまとめてダメージを与えることができます。

• より厳密に言い換えると、$1$ 以上 $10^9\ -\ D\ +\ 1$ 以下の 整数 $x$ を選んで、$x$ 列目から $x\ +\ D\ -\ 1$ 列目に (一部でも) 存在するすべての破壊されていない壁にパンチによるダメージを与えることができます。

壁は一部分でもダメージを受けると、パンチの衝撃波により全体が木っ端みじんに破壊されてしまいます。
(入出力例 $1$ の説明も参考にしてください。)

高橋君がすべての壁を破壊するには、少なくとも何回のパンチを放つ必要がありますか？

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すべての壁を破壊するのに必要なパンチの最少回数を出力せよ。

题目大意

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

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

Translated by @xiaomuyun

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$
• 入力はすべて整数である。

Sample Explanation 1

入力例 $1$ に対応する壁の配置を図示したものが下図です。  たとえば次のようにパンチを放つことで、 $2$ 回のパンチですべての壁を破壊することができます。(以下の説明では、$a$ 列目から $b$ 列目までの範囲を $\lbrack\ a,\ b\ \rbrack$ と表記します。) - まず、 $\lbrack\ 2,\ 4\ \rbrack$ にパンチを放つ。 $\lbrack\ 2,\ 4\ \rbrack$ に存在する壁である壁 $1$ と壁 $2$ はダメージを受け、破壊される。 - 次に $\lbrack\ 5,\ 7\rbrack$ にパンチを放つ。$\lbrack\ 5,\ 7\rbrack$ に存在する壁 $3$ はダメージを受け、破壊される。 また、次の方法でもすべての壁を $2$ 回のパンチで破壊することができます。 - まず、$\lbrack\ 7,\ 9\ \rbrack$ にパンチを放ち、壁 $2$ と壁 $3$ を破壊する。 - 次に、$\lbrack\ 1,\ 3\ \rbrack$ にパンチを放ち、壁 $1$ を破壊する。

Sample Explanation 2

入出力例 $1$ と比べると、壁 $3$ の範囲が $\lbrack\ 5,\ 9\ \rbrack$ から $\lbrack\ 4,\ 9\ \rbrack$ に変わりました。 この場合は $\lbrack\ 2,\ 4\ \rbrack$ にパンチを放つことで $1$ 回ですべての壁を破壊できます。