配点 : $400$ 点

問題文

$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$ の説明も参考にしてください。)

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

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq D \leq 10^9$
• $1 \leq L_i \leq R_i \leq 10^9$
• 入力はすべて整数である。

入力

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

$N$ $D$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

出力

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

3 3
1 2
4 7
5 9

2

入力例 $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$ を破壊する。

3 3
1 2
4 7
4 9

1

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

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

3