一个鸭子猎人正在做他最喜欢的事情,狩猎。他生活在一个二维世界中,位于点(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 处射击以击中三只鸭子。