Problem: Problem

Great Demon King Megumi wants to defeat the $ N $ hero who lives on the ground.
Megumi can cast explosion magic up to $ M $ times.
Explosion magic is magic that extinguishes heroes who exist within a radius of $ r $ around arbitrary coordinates.
The hero is very thin, so you don't have to consider the size.
All $ M $ explosion spells shall be cast with the same radius.
I decided to use the magic of the minimum radius necessary to annihilate the hero.
Minimize the size of the explosive magic radius.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq M \ leq N \ leq 14 $
* $ 0 \ leq x_i $, $ y_i \ leq 10 ^ 5 $

Input


$ N $ $ M $
$ x_1 $ $ y_1 $
...
$ x_N $ $ y_N $


The input is given in the following format.
The number of heroes $ N $ and the number of explosions to cast $ M $ are given as integers on the first line.
From the second line onward, the coordinates $ x_i $ $, $ $ y_i $ of each hero $ i $ are given as integers.

Output

Output the minimum value of the explosive magic radius as a real number.
Must not contain absolute error greater than $ 10 ^ {-3} $.

Examples

Input

5 2
0 0
5 5
10 10
100 100
200 200


Output

70.710678118755


Input

10 5
321 675
4312 6534
312 532
412 6543
21 43
654 321
543 0
32 5
41 76
5 1


Output

169.824909833728


Input

14 3
312 342
4893 432
321 4
389 4
23 543
0 0
1 1
2 2
432 12
435 32
1 5
2 10
100 100
20 50


Output

218.087711712613


Input

5 2
0 0
0 0
0 0
0 0
0 0


Output

0.000000000001

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }


const int MAX_V = 2000; /////////////////////////////////////////////////////////////

struct Edge{ int to,cap,rev; };

vector<Edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cap){
  G[from].push_back((Edge){to,cap,(int)G[to].size()});
  G[to].push_back((Edge){from,0,(int)G[from].size()-1});
}

int dfs(int v,int t,int f){
  if( v == t ) return f;
  used[v] = true;
  for(int i=0;i<(int)G[v].size();i++){
    Edge &e = G[v][i];
    if( !used[e.to] && e.cap > 0 ){
      int d = dfs(e.to,t,min(f,e.cap));
      if( d > 0 ){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s,t,INT_MAX);
    if( f == 0 ) return flow;
    flow += f;
  }
}

void init(int _size=MAX_V){ rep(i,_size) G[i].clear(); }



class Point{
public:
  double x,y;

  Point(double x = 0,double y = 0): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }

  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }

  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }

};

struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator <  (const Segment& s) const { return ( p2 == s.p2 ) ? p1 < s.p1 : p2 < s.p2; }
  bool operator == (const Segment& s) const { return ( s.p1 == p1 && s.p2 == p2 ) || ( s.p1 == p2 && s.p2 == p1 ); }

};

typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;

ostream& operator << (ostream& os,const Point& a){ return os << "(" << a.x << "," << a.y << ")"; }

ostream& operator << (ostream& os,const Segment& a){ return os << "( " << a.p1 << " , " << a.p2 << " )"; }

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }

// 度をラジアンに変換
double toRad(double agl){ return agl*M_PI/180.0; }

// a => prev, b => cur, c=> next
// prev から cur へ行って next へ行く際の角度を求める
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}






int N,M;
Point ps[111];

int dp[20*20*20][1<<14];
int calc(int n,double r) {
  vector<int> vec;

  rep(i,n) {
    int bits = 0;
    rep(j,n) {
      if( LTE(abs(ps[i]-ps[j]),r) ) {
	bits |= (1<<j);
      }
    }
    vec.push_back(bits);
  }
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i == j)continue;
      Point Rr = ps[i]-ps[j];
      if(abs(Rr) <= r*2+EPS || 1){
	Point UKPC,U,P1,P2;
	UKPC = (ps[i]+ps[j])*0.5;
	double l = abs(ps[i]-ps[j]) * 0.5;
	if( LTE(r * r - l * l,0)  ) continue;
	double T = sqrt(r*r-l*l);
	
	UKPC = (ps[i]+ps[j])*0.5;
	//P1 = UKPC + (ps[i]-point[j])/abs(point[i]-point[j])*polar(T,PI/2.0);
	Point uni = (ps[i] - ps[j]) / abs(ps[i]-ps[j]);
	//cout << "uni = " << uni <<endl;
	//P1 = UKPC + (T*((ps[i]-ps[j])/abs(ps[i]-ps[j])))*
	P1 = UKPC + rotate(uni,M_PI/2.0) * T;
	//P2 = UKPC + (ps[i]-point[j])/abs(point[i]-point[j])*polar(T,-PI/2.0);
	//P2 = UKPC + (ps[i]-ps[j])/abs(ps[i]-ps[j])*rotate(T,-M_PI/2.0);
	P2 = UKPC + rotate(uni,-M_PI/2.0) * T;
	/*
	puts("");
	cout << ps[i] << " and " << ps[j] << endl;
	cout << "UKPC = " << UKPC << endl;
	cout << "T = " << T << endl;
	cout << "P1 = " << P1 << ", P2 = " << P2 << endl;
	*/
	//cout << ps[i] << " and " << ps[j] <<endl;;
	double Calc;
	int bits = 0;
	for(int k=0;k<n;k++){
	  Calc = abs(P1-ps[k]);
	  if(fabs(Calc) < r+EPS){
	    bits |= (1<<k);
	  }
	}
	//bitset<5> BIT(bits);
	//cout << BIT << endl;
	vec.push_back(bits);
	bits = 0;
	for(int k=0;k<n;k++){
	  Calc = abs(P2-ps[k]);
	  if(fabs(Calc) < r+EPS){
	    bits |= (1<<k);
	  }
	}
	//BIT = bits;
	//cout << BIT << endl;
	vec.push_back(bits);
 
      }
 
    }
  }
  assert(vec.size()<20*20*20);
  int len = vec.size();
  rep(i,len+1) rep(j,(1<<n)) {
    dp[i][j] = INT_MAX;
  }
  dp[0][0] = 0;

  rep(i,len) {
    rep(j,(1<<n)) {
      int bits = vec[i];
      dp[i+1][j] = min(dp[i+1][j|bits],dp[i][j]);
      if( dp[i][j] == INT_MAX ) continue;
      dp[i+1][j|bits] = min(dp[i+1][j|bits],dp[i][j]+1);

    }
  }
  int resp = dp[len][(1<<n)-1];
  return resp;
}

bool check(double r) {
  return calc(N,r) <= M;
}

void compute() {
  double L=0,R=100000000;//fewopajfeaw
  rep(_,100) {//feoajfewao
    double _M = ( L + R ) * 0.5;
    if( check(_M) ) {
       R = _M;
    } else {
      L = _M;
    }
  }
  printf("%.10f\n",L);
}

int main() {
  cin >> N >> M;
  rep(i,N) cin >> ps[i].x >> ps[i].y;
  compute();
  return 0;
}