D - Destroyer Takahashi
当前没有测试数据。
D - Takahashi的毁灭者
分数：$400$分
题目描述
在一个被划分为$N$行$10^9$列的城镇中，有$N$面墙，编号为$1$到$N$。
第$i$面墙从第$i$行的左边起第$L_i$列延伸到第$i$行的右边第$R_i$列。 (参见样例输入和输出1中的图。)
Takahashi决定要毁灭所有$N$面墙。
因为他的超人力量，他可以一拳同时摧毁连续的$D$列。
- 更具体地说，他可以选择一个在$1$到$10^9 - D + 1$之间（包括边界）的整数$x$，将所有存在（或部分存在）在第$x$到$(x + D - 1)$列的墙壁造成破坏。
当墙壁的一部分被破坏时，整个墙壁将被拳击影响而被摧毁。
(参见样例输入和输出1中的图。)
至少需要Takahashi打多少次拳才能毁灭所有墙壁呢？
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq D \leq 10^9$
- $1 \leq L_i \leq R_i \leq 10^9$
- 输入中的所有值均为整数。
输入
输入以以下格式从标准输入给出：
输出
输出最少需要的拳数来毁灭所有墙壁。
3 3
1 2
4 7
5 9
2
下图描述了样例输入1中墙壁的排列。
他可以用两拳摧毁所有墙壁，如下所示。 （下图中，$\lbrack a, b \rbrack$表示第$a$列到$b$列的范围。）
- 首先，他用一拳摧毁$\lbrack 2, 4 \rbrack$范围的墙壁。这个范围内存在的墙壁――墙壁$1$和墙壁$2$――受到破坏并摧毁。
- 然后，他用一拳摧毁$\lbrack 5, 7 \rbrack$范围的墙壁。这个范围内存在的墙壁――墙壁$3$――受到破坏并摧毁。
也可以用如下的两拳摧毁全部墙壁：
- 首先，他用一拳摧毁$\lbrack 7, 9 \rbrack$范围的墙壁，摧毁了墙壁$2$和墙壁$3$。
- 然后，他用一拳摧毁$\lbrack 1, 3 \rbrack$范围的墙壁，摧毁了墙壁$1$。
3 3
1 2
4 7
4 9
1
与样例输入输出1的区别是墙壁$3$现在覆盖范围是$\lbrack 4, 9 \rbrack$而不是$\lbrack 5, 9 \rbrack$。
在这种情况下，他可以用一拳摧毁$\lbrack 2, 4 \rbrack$范围的墙壁。
5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000
3
与样例输入输出2的区别是墙壁$1$和墙壁$2$有共同的范围$\lbrack 1, 100 \rbrack$。
在这种情况下，他可以用三拳摧毁所有墙壁。