← 返回题目列表

Codeforces · 542/B

B. 狩猎鸭子

中文机器翻译题面 查看原题

一个鸭子猎人正在做他最喜欢的事情,狩猎。他生活在一个二维世界中,位于点(0, 0)。由于他不喜欢步行寻找猎物,因此他更喜欢仅垂直向上射击(因为在这种情况下,鸭子会直接落入他的手中)。猎人不会立即重新装弹——两次射击之间必须经过r或更多秒。当猎人向上射击时,子弹立即击中猎人正上方的所有鸭子。

在二维世界中,每只鸭子都是一个水平段,以每秒 1 个长度单位的速度沿 Ox 轴的负方向水平移动。对于每只鸭子,我们知道值 hi 和 ti — 时间 0 时其头部(线段的左端)和尾部(线段的右端)的 x 坐标。鸭子飞行的高度并不重要,因为枪垂直射击到无限高度并击中途中的所有鸭子。

第一个示例的图。

猎人最多可以射杀多少只鸭子?如果鸭子在射击时至少有一个点与 Oy 轴相交,则认为鸭子已被猎人射击。猎人射中鸭子后,鸭子就摔倒了,再也不能射了。猎人在时间 0 之前不能射击。

输入

输入的第一行包含整数 n, r (1 ≤ n ≤ 200 000, 1 ≤ r ≤ 109) — 鸭子的数量和两次射击之间的最短时间(以秒为单位)。

接下来n行,每行包含两个整数hi, ti (- 109 ≤ hi < ti ≤ 109)——第i只鸭子在0时刻的头和尾的x坐标。

输出

打印一个整数——猎人可以射杀的鸭子的最大数量。

示例

输入 #1

3 3
-3 0
1 3
-1 2

输出 #1

3

输入 #2

4 5
-1 1
2 4
5 9
6 8

输出 #2

3

注意

在第一个样本中,猎人必须在时间 0 射击,这一枪杀死了鸭子 1 和 3。然后猎人需要重新装弹并在时间 3 再次射击。他的第二次射击击中了鸭子 2 的尾巴。

在第二个示例中,猎人可以在时间 0 和 6 处射击以击中三只鸭子。