#include <bits/stdc++.h>

using namespace std;

using u32=unsigned int;
using i64=long long;
using u64=unsigned long long;
using db=double;
using vi=vector<int>;
using pii=pair<int,int>;

template<typename T>
T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch-'0'),ch=getchar();
    return f?-x:x;
}

#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define pb push_back

const int N=5010,INF=0x3f3f3f3f,MX=2000;

int n,m;
pii p[N];

template<typename T>
void ckmin(T &a,T b){
    if(a>b) a=b;
}
template<typename T>
void ckmax(T &a,T b){
    if(a<b) a=b;
}

void solve(int tid){
    n=rdi(),m=rdi();
    for(int i=1;i<=n;i++){
        int x=rdi(),y=rdi();
        p[i]={x-y,x+y};
    }
    static int f[5][(MX+1)*8][2];
    const int DT=MX*4;
    f[0][0][0]=f[0][0][1]=0;
    for(int i=1;i<=4;i++){
        for(int k=-MX*i;k<=MX*i;k++)
            f[i][k+DT][0]=INF,f[i][k+DT][1]=-INF;
        for(int j=1;j<=n;j++){
            int v1,v2;
            if(i==1) v1=p[j].fi,v2=p[j].se;
            else if(i==2) v1=p[j].se,v2=-p[j].fi;
            else if(i==3) v1=-p[j].fi,v2=-p[j].se;
            else if(i==4) v1=-p[j].se,v2=p[j].fi;
            for(int k=-MX*(i-1);k<=MX*(i-1);k++){
                if(f[i-1][k+DT][0]==INF) continue;
                ckmin(f[i][k+v1+DT][0],f[i-1][k+DT][0]+v2);
                ckmax(f[i][k+v1+DT][1],f[i-1][k+DT][1]+v2);
            }
        }
    }

    auto dis2 = [&](i64 x,i64 y){
        return (db)x*x+(db)y*y;
    };

    db ans=0;
    vector<pii> vec[5];
    for(int i=1;i<=4;i++)
        for(int x=-MX*i;x<=MX*i;x++){
            if(f[i][x+DT][0]==INF) continue;
            for(auto y:f[i][x+DT]) vec[i].pb({x,y});
        }
    for(int i=1;i<=min(4,m);i++){
        for(auto cur:vec[i]){
            int x=cur.fi,y=cur.se,mul=(i!=4?1:m/4);
            ans=max(ans,dis2((i64)x*mul,(i64)y*mul));
            // int c=(m-i)/4;
            // for(auto cur1:vec[4])
            //     ans=max(ans,dis2(x+(i64)c*cur1.fi,y+(i64)c*cur1.se));
        }
    }
    printf("Case #%d: %.10lf\n",tid,sqrt(ans));
}

int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int T=rdi();
    for(int i=1;i<=T;i++) solve(i);
    return 0;
}