秋葵的J型探测器

秋葵的J型探测器

Background

把妹王秋葵不仅有极高的“人格魅力”,更拥有可以探测plmm的法宝——J型探测器。

Description

通常秋葵为了寻找猎物会在一条笔直的街道上行走(假定为无限长)。而探测器的探测范围为r,当plmm与探测器的距离不超过r时,该plmm可以被搜到。在这里,我们引用笛卡尔坐标系,定义秋葵寻找猎物的街道为x轴,而plmm们分布在x轴的上方与下方。而plmm们被秋葵的人格魅力所感染,因此并不会走动,而选择欣赏秋葵的人格魅力。而因为plmm间隔过远,所以秋葵需要走马观花(即在x轴上移动)并在指定位置停下才能尽量探测并观望所有的plmm。现在给出plmm们的坐标以及J型探测器的探测范围,请你求出能够让秋葵探测并观望到所有plmm至少需要在x轴上在不同的位置停留几次(初始位置也算)。

Format

1≤n≤1000 (1s/64mb)

Input

第一行输入两个整数n和r,分别为plmm的个数与探测距离。
接下来n行,每行输入两个整数,分别代表plmm的x,y轴坐标。

Output

输出一个整数,代表所需的最少的观测位置,若没有解决方案则所需数目输出“-1”。

Sample 1

Input

3 2
1 2
-3 1
2 1

Output

2

信息

ID
1002
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
1
上传者

相关

在下列训练计划中:

萌新院程序能力测试题集

在下列比赛中:

萌新院程序设计能力检测Round1