Score : $400$ points

问题描述

在一个被划分为 $N$ 行和 $10^9$ 列网格的小镇上，有 $N$ 道墙，编号从 $1$ 到 $N$。 第 $i$ 道墙位于顶部第 $i$ 行，从左边第 $L_i$ 列延伸至第 $R_i$ 列。（参见示例输入与输出 $1$ 中的图示）

高桥决定摧毁所有这 $N$ 道墙。凭借其超人的力量，他的一拳可以一次性破坏连续的 $D$ 列。

• 更正式地讲，他可以选择一个 整数 $x$，满足 $1 \leq x \leq 10^9 - D + 1$（包括两端），来破坏所有存在于（或部分存在于）第 $x$ 到 $(x + D - 1)$ 列之间且尚未被摧毁的墙。

当墙的一部分被破坏时，该整面墙会因拳头的冲击而被完全摧毁。 （参见示例输入与输出 $1$ 中的图示）

高桥至少需要出拳多少次才能摧毁所有墙壁？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

In a town divided into a grid with $N$ rows and $10^9$ columns, there are $N$ walls, numbered $1$ to $N$.
Wall $i$ ranges from the $L_i$-th column to the $R_i$-th column from the left in the $i$-th row from the top. (See also the figure at Sample Input and Output $1$.)

Takahashi has decided to destroy all $N$ walls.
With his superhuman strength, his one punch can damage consecutive $D$ columns at once.

• More formally, he can choose an integer $x$ between $1$ and $10^9 - D + 1$ (inclusive) to damage all walls that exist (or partly exist) in the $x$-th through $(x + D - 1)$-th columns and are not yet destroyed.

When a part of a wall is damaged, that whole wall will be destroyed by the impact of the punch.
(See also the figure at Sample Input and Output $1$.)

At least how many times does Takahashi need to punch to destroy all walls?

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq D \leq 10^9$
• $1 \leq L_i \leq R_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $D$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

Output

Print the minimum number of punches needed to destroy all walls.

Sample Input 1

3 3
1 2
4 7
5 9

Sample Output 1

2

The figure below describes the arrangements of walls in Sample Input $1$.

He can destroy all walls with two punches, such as the following. (Below, $\lbrack a, b \rbrack$ denotes the range from the $a$-th through $b$-th columns.)

• First, punch $\lbrack 2, 4 \rbrack$. The walls existing in $\lbrack 2, 4 \rbrack$ ― Walls $1$ and $2$ ― are damaged and destroyed.
• Second, punch $\lbrack 5, 7 \rbrack$. The wall existing in $\lbrack 5, 7 \rbrack$ ― Wall $3$ ― is damaged and destroyed.

It is also possible to destroy all walls with two punches in this way:

• First, punch $\lbrack 7, 9 \rbrack$ to destroy Walls $2$ and $3$.
• Second, punch $\lbrack 1, 3 \rbrack$ to destroy Wall $1$.

Sample Input 2

3 3
1 2
4 7
4 9

Sample Output 2

1

The difference from Sample Input/Output $1$ is that Wall $3$ now covers $\lbrack 4, 9 \rbrack$, not $\lbrack 5, 9 \rbrack$.
In this case, he can punch $\lbrack 2, 4 \rbrack$ to destroy all walls with one punch.

Sample Input 3

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

Sample Output 3

3

update @ 2024/3/10 10:03:32