P. [ABC230D] Destroyer Takahashi

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个 $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$

输出最少打拳的次数

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