4000 - 【提高组】第二课:雷达

有n个二维坐标点。

现在要在x轴上放置若干雷达,每个雷达的辐射半径都是d。

问至少需要几个雷达,才能够幅射所有点,如果辐射不到所有的点,则输出-1。

15831619305960.png

输入

第一行一个整数$ n(1 \le n \le 1000) $ 和 $ d(1 \le d \le 10000) $。

接下来n行,每行输入一个点的坐标。

坐标范围[-10000,10000]。

输出

输出一个整数表示答案。

样例

输入

3 2
1 2
-3 1
2 1

输出

2

输入

1 2
0 2

输出

1

提示

子任务1,20分,$ 1 \le n \le 10 $ , $ 1 \le d \le 10 $,坐标范围[-10,10]。

子任务2,30分,$ 1 \le n \le 100 $ , $ 1 \le d \le 100 $,坐标范围[-100,100]。

子任务3,50分,$ 1 \le n \le 1000 $ , $ 1 \le d \le 10000 $,坐标范围[-10000,10000]。

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题