#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> coordinates;
vector ingredient;
vector distance;
long double dp[1<<13][36];
int dist[50][50]={0};
int n,k;
string temp;
long double ecluidDistance(pair<int ,int> p1,pair<int,int> p2){
int dx = p1.first - p2.first;
int dy = p1.second - p2.second;
return sqrt(dxdx + dydy);
}
long double showtrip(int mask,int idx){
if(mask==((1<<k)-1) and idx==0){
return 0;
}
if(dp[mask][idx]!=-1){
return dp[mask][idx];
}
dp[mask][idx]=INT_MAX;
for(int i=0;i<=n;i++){
if((mask|ingredient[i])!=mask ||(i==0)){
dp[mask][idx] = min(dp[mask][idx],dist[idx][i]+showtrip(mask|ingredient[i],i));
}
}
return dp[mask][idx];
}
int main()
{
int t;
cin>>t;
while(t–){
coordinates.clear();
ingredient.clear();
cin>>n>>k;
coordinates.push_back(make_pair(0,0));
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
coordinates.push_back(make_pair(x,y));
}
ingredient.push_back(0);
int possible = 0;
for(int i=0;i<n;i++){
cin>>temp;
reverse(temp.begin(),temp.end());
int temp_mask = 0;
for(int j=0;j<temp.length();j++){
temp_mask |= ((1<<j)*(temp[j]-'0'));
}
possible |= temp_mask;
ingredient.push_back(temp_mask);
}
int ans_ = ((1<<k)-1);
if(ans_ != possible){
cout<<"-1"<<endl;
continue;
}
memset(dist,0,sizeof(dist));
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dist[i][j] = ecluidDistance(coordinates[i],coordinates[j]);
}
}
for(int i=0;i<(1<<13);i++){
for(int j=0;j<=n;i++){
dp[i][j]=-1;
}
}
long double result = showtrip(0,0);
cout<<fixed<<setprecision(9)<<result<<endl;
}
}