Problem: Problem Statement

In A.D. 2101, war was beginning. The enemy has taken over all of our bases. To recapture the bases, we decided to set up a headquarters. We need to define the location of the headquarters so that all bases are not so far away from the headquarters. Therefore, we decided to choose the location to minimize the sum of the distances from the headquarters to the furthest $K$ bases. The bases are on the 2-D plane, and we can set up the headquarters in any place on this plane even if it is not on a grid point.

Your task is to determine the optimal headquarters location from the given base positions.

* * *

Input

The input consists of a single test case in the format below.

> $N$ $K$ $x_{1}$ $y_{1}$ $\vdots$ $x_{N}$ $y_{N}$

The first line contains two integers $N$ and $K$. The integer $N$ is the number of the bases ($1 \le N \le 200$). The integer $K$ gives how many bases are considered for calculation ($1 \le K \le N$). Each of the following $N$ lines gives the x and y coordinates of each base. All of the absolute values of given coordinates are less than or equal to $1000$, i.e., $-1000 \le x_{i}, y_{i} \le 1000$ is satisfied.

Output

Output the minimum sum of the distances from the headquarters to the furthest $K$ bases. The output can contain an absolute or a relative error no more than $10^{-3}$.

Examples

Input| Output
---|---


3 1
0 1
1 0
1 1


|


0.70711



6 3
1 1
2 1
3 2
5 3
8 5
13 8


|


17.50426



9 3
573 -50
-256 158
-751 14
314 207
293 567
59 -340
-243 -22
-268 432
-91 -192


|


1841.20904






Example

Input




Output

Solution (in CPP):

Solution:
   #include <bits/stdc++.h>
 
//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-8)
                                          
    int dx[8]={0,1,0,-1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x;
                                   				int y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	int x;
                                            	int y,z,w;
                                            	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            
 
                      
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                            
                                int mod;
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
pa operator+(const pa & l,const pa & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}    
pa operator-(const pa & l,const pa & r) {   
    return {l.first-r.first,l.second-r.second};                                    
}  
                                
                int pr[1000010];
                int inv[1000010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	wa%=warukazu;
                	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
                	ll zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }
 
                
    			int comb(int nn,int rr){
    				if(rr<0 || rr>nn || nn<0) return 0;
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
               
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<=ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                		inv[ert]=beki(pr[ert],mod-2,mod);
                	for(int i=ert-1;i>=0;i--){
                		inv[i]=inv[i+1]*(i+1)%mod;
                	}
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
 //   mt19937(clock_per_sec);
  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
      
       
       
                               //----------------kokomade tenpure------------
 
vector<pair<double,double>> ve;



int n,k;

double hoge(double x,double y){
	return sqrt(x*x+y*y);
}
double ss(double x,double y){
	vector<double> V;
	
	for(auto v:ve){
		V.pb(-hoge(x-v.first,y-v.second));
	}
	sort(V.begin(),V.end());
	double ans=0;
	for(int i=0;i<k;i++)ans-=V[i];
	return ans;
}


double s(double x){
	
	double si=-10000,ue=10000;
 	for(int i=0;i<100;i++){
 		double me1=(ue+si*2)/3;
 		double me2=(ue*2+si)/3;
 		
 		double f1=ss(x,me1);
 		double f2=ss(x,me2);
 		
 		if(f1<f2)ue=me2;
 		else si=me1;
 		
 	}
	
	return ss(x,((ue+si)/2));
	
}

 signed main(){
 	
 
   cin.tie(0);
	ios::sync_with_stdio(false);
	
	double si=-10000,ue=10000;
 	cin>>n>>k;
 	for(int i=0;i<n;i++){
 		double x,y;
 		cin>>x>>y;
 		ve.pb(mp(x,y));
 	}
 	for(int i=0;i<100;i++){
 		double me1=(ue+si*2)/3;
 		double me2=(ue*2+si)/3;
 		
 		double f1=s(me1);
 		double f2=s(me2);
 		
 		if(f1<f2)ue=me2;
 		else si=me1;
 		
 	}
 	printf("%.10lf\n",s((ue+si)/2));
 	
 //	cout<<s<<endl;
return 0;
 
 }