#include<bits/stdc++.h>
#define int long long//与基准判时,值域最大3e16，不会爆long long
using namespace std;
int read() {
	char ch=getchar();int res=0,fl=1;
	while(ch<'0'||ch>'9'){if(ch=='-') fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
	return res*fl;
}
const int N=5005;
struct vec{
	int x,y;
}a[N][4],p[4];
vec operator +(vec A,vec B){return (vec){A.x+B.x,A.y+B.y};}
vec operator *(vec A,int k){return (vec){A.x*k,A.y*k};}
vec operator *(int k,vec A){return (vec){A.x*k,A.y*k};}
int operator *(vec A,vec B){return A.x*B.x+A.y*B.y;}
double dis(vec A){return sqrt(1.0*A.x*A.x+1.0*A.y*A.y);}//自乘可能爆long long!!要用double
int n,m,test_case=0;
double calc(vec lim) {
	for(int k=0;k<4;++k) {
		p[k]=a[1][k];//可能不如0，一定要注意!!
		for(int i=2;i<=n;++i) p[k]=((p[k]*lim)<(a[i][k]*lim))?a[i][k]:p[k];
	}
/*	vec ans=(vec){0,0},res=(vec){0,0};
	for(int i=1;i<=m;++i) {
		res=res+p[(i-1)%4];
		if((res*lim)>(ans*lim)) ans=res;
	}//!!!我这块求max写错了!!
	return dis(ans);*/
	vec v[4],ans,base=p[0]+p[1]+p[2]+p[3];
	v[0]=(vec){0,0};
	ans=v[0];
	v[1]=p[0];
	v[2]=p[0]+p[1];
	v[3]=p[0]+p[1]+p[2];
	if(m<4) {
		for(int i=0;i<=m;++i) if((v[i]*lim)>(ans*lim)) ans=v[i];
		return dis(ans);//
	}
	else {
		for(int i=0;i<4;++i) {
			vec tmp=v[i];
			if((base*lim)>0) tmp=tmp+(base*((m-i)/4));
			if((tmp*lim)>(ans*lim)) ans=tmp;
		}
		return dis(ans);
	}
	/*	vec base=p[0]+p[1]+p[2]+p[3],ans=(vec){0,0};
	ans=ans+(((base*lim)>0)?(base*max((m/4)-1,0ll)):(vec){0,0});
	m=m-4*max((m/4)-1,0ll);//把>=8的部分都减4
	vec v[8],maxn;
	v[0]=(vec){0,0};
	maxn=v[0];
	for(int i=1;i<=7;++i) {
		v[i]=v[i-1]+p[(i-1)%4];
		if(m>=i&&(v[i]*(lim))>(maxn*lim)) maxn=v[i];
	} 
//	if(m>=1&&(v0*lim)>(maxn*lim)) maxn=v0;
//	if(m>=2&&(v1*lim)>(maxn*lim)) maxn=v1;
//	if(m>=3&&(v2*lim)>(maxn*lim)) maxn=v2;
//	printf("(%d,%d)(%d,%d)\n",maxn.x,maxn.y,ans.x,ans.y);
	return dis(ans+maxn);*/
}
void solve() {
	test_case++;
	double Ans=0.0;
	n=read();m=read();
	for(int i=1;i<=n;++i) {
		int x=read(),y=read();
		a[i][0]=(vec){(x-y),(x+y)};
		a[i][1]=(vec){(x+y),-(x-y)};
		a[i][2]=(vec){-(x-y),-(x+y)};
		a[i][3]=(vec){-(x+y),x-y};
	}
//	for(int i=1;i<=n;++i) printf("(%lld,%lld)(%lld,%lld)(%lld,%lld)(%lld,%lld)\n",a[i][0].x,a[i][0].y,a[i][1].x,a[i][1].y,a[i][2].x,a[i][2].y,a[i][3].x,a[i][3].y);
	for(int i=1;i<=10000;++i) {
		int x=(1ll*rand()*rand()-1ll*rand()*rand())%100000,y=(1ll*rand()*rand()-1ll*rand()*rand())%100000;
		Ans=max(Ans,calc((vec){x,y}));
	}
	printf("Case #%lld: %.10lf\n",test_case,Ans);
	return ;
}
signed main()
{
	//freopen("freedom.in","r",stdin);
	//freopen("freedom.out","w",stdout);
	int T=read();
	while(T--) {
		solve();
	}
	return 0;
}