雷达安装

题目描述

假设海岸线是一条无限延伸的直线。它的一侧是陆地,另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上(包括海岸线),并且每个雷达都有相同的扫描范围 $d$。你的任务是建立尽量少的雷达站,使所有小岛都在扫描范围之内。 数据使用笛卡尔坐标系,定义海岸线为 $x$ 轴。在 $x$ 轴上方为海洋,下方为陆地。

输入输出格式

输入格式


第一行包括 $2$ 个整数 $n$ 和 $d$,$n$ 是岛屿数目,$d$ 是雷达扫描范围。 接下来 $n$ 行,每行两个整数,为岛屿坐标。

输出格式


一个整数表示最少需要的雷达数目,若不可能覆盖所有岛屿,输出 `-1`。

输入输出样例

输入样例 #1

3 2
1 2
-3 1
2 1

输出样例 #1

2

说明

### 样例 1 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/fnezefht.png) ### 数据范围 对于全部数据,$n\le1000$,$ d \le 2\times 10^4$,$ | x_i | \le 2 \times 10^6 $,$ 0 \le y_i \le 2\times 10^4$。