/*转载请注明出处：乄心-小黄豆http://blog.csdn.net/wuxinxiaohuangdou*/
题目大意：在x轴上建立尽量少的雷达覆盖所有的岛屿。
Input：岛屿的数量n，雷达覆盖半径d.接下来的n行一行表示一个岛屿(x,y).
Output:每个案例的雷达最少数目.
经典的区间选点！
要搞清楚为什么排序，然后要明白如何选点。
思想（排序原因）：小区间被满足，大区间一定被满足。
(所以排序后所有岛屿都是 递增的！)(即小区间都在前面。)
选点：只有前一个点的右端点小于下一个点的左端点，这时才选一个点（即增加一个雷达）因为不可能存在一个雷达可以覆盖到这两个岛屿，而且此时前面用一个雷达覆盖即为最优解！（因为大区间包含了小区间）
/*63MS 区间选点问题!*/
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
double d;
int num=1;
class Node
{
public:
double x,y; //点坐标
double left,right; //在x轴上雷达能够覆盖到该点的范围。
double qu_lenth; //该范围长度。
bool operator<(const Node& t) const
{
if(right!=t.right)
return right<t.right; //（右端点不等时）把右端点从小到大排序。
else
return qu_lenth<t.qu_lenth; //否则把长度从小到大排序。
}
}a[1010];
double right_dis(double x0,double y0) //计算右端点
{
double x=sqrt(d*d-y0*y0)+x0;
return x;
}
double left_dis(double x0,double y0) //计算左端点
{
double x=-sqrt(d*d-y0*y0)+x0;
return x;
}
int main()
{
int i;
while(true)
{
int ok=1;
int count=1;
cin>>n>>d;
if(n==0&&d==0) break;
if(n==0||d==0) //岛数为0，或雷达半径为0，都直接输出-1.
{
cout<<"Case "<<num++<<": -1"<<endl;
continue;
}
for(i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
if(a[i].y>d) //如果某个岛的垂直距离(即y)大于雷达的覆盖半径，那么肯定无解，直接在后输出-1。
{
ok=0;
}
a[i].right=right_dis(a[i].x,a[i].y); //得到每个岛的数据。
a[i].left=left_dis(a[i].x,a[i].y);
a[i].qu_lenth=fabs(a[i].right-a[i].left);
//cout<<"a[i].right="<<a[i].right<<" "<<"a[i].left="<<a[i].left<<endl;
}
if(ok==0)
{
cout<<"Case "<<num++<<": -1"<<endl;
continue;
}
sort(a+1,a+n+1); //给岛(相当于区间的点)进行排序.
double temp;
temp=a[1].right; //从第一个岛的右端点开始。
for(i=2;i<=n;i++) //枚举到最后个岛
{
if(temp<a[i].left) //一旦前面一个岛的右端点小于后一个岛的左端点.
{
temp=a[i].right; //就把这个岛的右端点给temp。
count++; //这个时候雷达的数量就加1。
}
}
cout<<"Case "<<num++<<": "<<count<<endl;
}
return 0;
}