Problem: Problem

Chocolate company Chinor Choco has decided to build n new stores.
For each store, ask each store manager to prepare two candidates for the place you want to build, and build it in either place.

Chinor Choco sells m types of chocolate, each manufactured at a different factory.
All types of chocolate are sold at all stores.
Chinor Choco owns only one truck to transport chocolate, and one truck can only carry one store's worth of chocolate.
Therefore, trucks need to go around all factories when moving from one store to another.

Find the maximum travel distance when the stores are arranged so that the maximum minimum travel distance when moving from one store to another is the minimum.

There can be multiple stores and factories in the same location.

Constraints

The input satisfies the following conditions.

* 2 ≤ n ≤ 200
* 1 ≤ m ≤ 15
* 0 ≤ ai, bi, ci, di, xi, yi ≤ 1000

Input

The input is given in the following format.


n m
a0 b0 c0 d0
...
an−1 bn−1 cn−1 dn−1
x0 y0
...
xm−1 ym−1


All inputs are given as integers.
On the first line, the number of Chinor chocolate shops n and the number of chocolate manufacturing factories m are given, separated by blanks.
From the second line to the nth line, the coordinates (ai, bi), (ci, di) of the candidate places to build each store are given separated by blanks.
2 & plus; Factory coordinates (xi, yi) are given from the nth line to the mth line, separated by blanks.

Output

Output the maximum travel distance when the store is arranged so that the maximum of the minimum travel distance is minimized.
The error should not exceed 10-6.

Examples

Input

2 1
0 0 5 5
3 3 6 6
2 2


Output

4.2426406871


Input

2 2
0 0 6 0
7 0 3 0
4 0
5 0


Output

3.0000000000

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
int exf=0;

struct closure{
  int ai,af,bi,bf; 
  closure(int ai,int af,int bi,int bf):
    ai(ai), af(af), bi(bi), bf(bf) {}
};


void add_edge(int from,int to,mat &G,mat &rG){
  G[from].push_back(to);
  rG[to].push_back(from);
}

void dfs(int v,const mat &G,vec &used,vec &vs){
  used[v]=1;
  for(int to:G[v])
    if(!used[to])
      dfs(to,G,used,vs);
  vs.push_back(v);
}

void rdfs(int v,int k,const mat &rG,vec &used,vec &cmp){
  used[v]=1;
  cmp[v]=k;
  for(int to:rG[v])
    if(!used[to])
      rdfs(to,k,rG,used,cmp);
}

int scc(const mat &G,const mat &rG,vec &cmp){
  int n=G.size();
  cmp=vec(n);
  vec vs, used(n,0);
  for(int v=0;v<n;v++){
    if(!used[v])dfs(v,G,used,vs);
  }
  int k=0;
  reverse(vs.begin(),vs.end());

  used=vec(n,0);
  for(int i=0;i<n;i++){
    int v=vs[i];
    if(!used[v])rdfs(v,k++,rG,used,cmp);
  }
  return k;
}


bool sat2(int n,const vector<closure> &A){

  
  int m=A.size();
  
  mat G,rG;
  G.resize(n*2);
  rG.resize(n*2);

  for(int i=0;i<m;i++){
    closure cl=A[i];
    int ai=cl.ai,bi=cl.bi;
    int af=cl.af,bf=cl.bf;
    
    if(!af && bf){
      swap(ai,bi);
      swap(af,bf);
    }
    if(af && !bf){
      add_edge(ai+n,bi+n,G,rG);
      add_edge(bi  ,ai  ,G,rG);
    }
    if(af && bf){
      add_edge(ai+n,bi,G,rG);
      add_edge(bi+n,ai,G,rG);
    }
    if(!af && !bf){
      add_edge(ai,bi+n,G,rG);
      add_edge(bi,ai+n,G,rG);
    }
  }
  
  vec cmp, res(n,0), tmp;
  scc(G,rG,cmp);
  for(int i=0;i<n;i++){
    if(cmp[i]==cmp[i+n])return false;
  }
  return true;
}


int n,m;
double ax[200],ay[200],bx[200],by[200];
double cx[15],cy[15];

double dp[15][1<<15][15];

double f(double ax,double ay,double bx,double by){
  double X=ax-bx;
  double Y=ay-by;
  return sqrt(X*X+Y*Y);
}

double calc(double ax,double ay,double bx,double by){
  double res=1e9;
  for(int i=0;i<m;i++){
    for(int j=0;j<m;j++){
      res=min(res,f(ax,ay,cx[i],cy[i])+dp[i][(1<<m)-1][j]+f(bx,by,cx[j],cy[j]));
    }
  }
  return res;
}

double Mem[300][2][300][2];
int used[300][2][300][2];
double Calc(int a,int af,int b,int bf){
  if(used[a][af][b][bf])return Mem[a][af][b][bf];
  used[a][af][b][bf]=1;
  double x0 = ( af == 0 ? ax[a] : bx[a] );
  double y0 = ( af == 0 ? ay[a] : by[a] );
  double x1 = ( bf == 0 ? ax[b] : bx[b] );
  double y1 = ( bf == 0 ? ay[b] : by[b] );
  return Mem[a][af][b][bf]=calc( x0,y0,x1,y1);
}

bool mem;
int lastsize=-1;

bool check(double mid){

  vector< closure > v;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      bool f00=(Calc(i,0,j,0) < mid );
      bool f01=(Calc(i,0,j,1) < mid );
      bool f10=(Calc(i,1,j,0) < mid );
      bool f11=(Calc(i,1,j,1) < mid );
      
      if( !f00 ){
        v.emplace_back(i,1,j,1 );
      }
      if( !f01 ){
        v.emplace_back(i,1,j,0 );
      }
      if( !f10 ){
        v.emplace_back(i,0,j,1 );
      }
      if( !f11 ){
        v.emplace_back(i,0,j,0 );
      }
    }
  }

  
  return mem  = sat2( n, v );
}

double solve(){
  for(int i=0;i<m;i++)
    for(int j=0;j<(1<<m);j++)
      for(int k=0;k<m;k++)
        dp[i][j][k]=1e9;

  double maxm=0,mini=0;
  
  for(int i=0;i<m;i++){
    dp[i][(1<<i)][i]=0;
    for(int bit=0;bit<(1<<m);bit++){
      for(int pos=0;pos<m;pos++){
        for(int to=0;to<m;to++){
          double dx=cx[pos]-cx[to];
          double dy=cy[pos]-cy[to];
          double cost=sqrt(dx*dx+dy*dy);
          int nbit=bit|(1<<to);
          dp[i][nbit][to]=min(dp[i][nbit][to],dp[i][bit][pos]+cost);

          maxm=max( maxm , dp[i][nbit][to] + 3000 );
          if(nbit==(1<<m)-1){
            mini=min( mini, dp[i][nbit][to]  );
          }
          
        }
      }
    }
  }
  
  double left=0,right=maxm,mid;
  
  for(int i=0;i<100;i++){
    mid=(left+right)*0.5;
    if( check(mid) ){
      exf=1;
      right=mid;
    }    else {
      exf=0;
      left=mid;
    }
  }
  return left;
}

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>ax[i]>>ay[i]>>bx[i]>>by[i];
  }
  for(int i=0;i<m;i++){
    cin>>cx[i]>>cy[i];
  }
  printf("%.10f\n",solve());
  return 0;
}