Duck Hunt

题面翻译

题目描述

猎人正在做他喜欢的事情，狩猎。他生活在一个二维世界，位于点$(0,0)$。因为他不喜欢为了猎物而行走，所以他更喜欢垂直向上射击（因为在这种情况下，鸭子会直接落入他的手中）。猎人不会立刻装填枪——两次射击之间必须经过$r$秒或更长的时间。当猎人射击时，子弹立即击中猎人正上方的所有鸭子。

在二维世界中，每个鸭子是水平片段，它们以每秒$1$单位长度的速度在$O_x$轴上沿负方向水平移动。对于每只鸭子，我们知道值$h_i$和$t_i$——它在时间$0$时的头部（片段的左端）和它的尾部（片段的右端）的$x$坐标。鸭子飞行的高度并不重要，因为枪可以垂直向上射到无限高度并击中它飞行轨迹上所有鸭子。

猎人射中的最大鸭子数量是多少？在射击时刻，若一只鸭子的任意一点与$O_y$轴相交，则该鸭子被认为是被猎人射中。在猎人射击鸭子后，它会掉下来，不能再被射击了。猎人不能在时间$0$之前射击。

输入输出格式

输入格式：

输入的第一行包含整数$n,r(1\leq n\leq 200000,1\leq r\leq 10^9)$——鸭子的数量和射击间隔的最短时间（以秒为单位）。

接下来$n$行，每行包含两个整数$h_i,t_i(-10^9\leq h_i<t_i\leq 10^9)$——第$i$只鸭在时间$0$时的头和尾的$x$坐标。

输出格式：

输出一个整数——猎人可以射中的最大鸭子数

说明

在第一个样例中，猎人必须在时间$0$射击，这次射击会杀死鸭子$1$和鸭子$3$。然后猎人需要重新装填枪并在时间$3$再次射击。他的第二枪击中了鸭子$2$的尾巴。 在第二个样例中，猎人可以在时间$0$和时间$6$射击以击中三只鸭子。

题目描述

A duck hunter is doing his favorite thing, hunting. He lives in a two dimensional world and is located at point $(0,0)$ . As he doesn't like walking for his prey, he prefers to shoot only vertically up (because in this case, the ducks fall straight into his hands). The hunter doesn't reload the gun immediately — $r$ or more seconds must pass between the shots. When the hunter shoots up, the bullet immediately hits all the ducks who are directly above the hunter.

In a two dimensional world each duck is a horizontal segment that moves horizontally in the negative direction of the $Ox$ axis at the speed $1$ length unit per second. For each duck we know the values $h_{i}$ and $t_{i}$ — the $x$ -coordinates of its head (the left end of the segment) and its tail (the right end of the segment) at time $0$ . The height where the duck is flying isn't important as the gun shoots vertically up to the infinite height and hits all the ducks on its way.

The figure to the first sample.What maximum number of ducks can the hunter shoot? The duck is considered shot by the hunter if at the moment of the shot at least one of its point intersects the $Oy$ axis. After the hunter shoots the duck, it falls and it can't be shot anymore. The hunter cannot make shots before the moment of time 0.

输入格式

The first line of the input contains integers $n$ , $r$ ( $1<=n<=200000$ , $1<=r<=10^{9}$ ) — the number of ducks and the minimum time in seconds between the shots.

Then $n$ lines follow, each of them contains two integers $h_{i},t_{i}$ ( -10^{9}<=h_{i}&lt;t_{i}<=10^{9} ) — the $x$ -coordinate of the head and tail of the $i$ -th duck at the moment $0$ .

输出格式

Print a single integer — the maximum number of ducks that can be shot by the hunter.

样例 #1

样例输入 #1

3 3
-3 0
1 3
-1 2

样例输出 #1

3

样例 #2

样例输入 #2

4 5
-1 1
2 4
5 9
6 8

样例输出 #2

3

提示

In the first sample the hunter must shoot at time 0, this shot kills ducks 1 and 3. Then the hunter needs to reload the gun and shoot again at time 3. His second shot hits the tail of duck 2.

In the second sample the hunter can make shots at times 0 and 6 to hit three ducks.