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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;


/* 幾何の基本 */

#include <complex>

typedef complex<ld> Point;


const ld pi = acos(-1.0);
const ld dtop = pi / 180.;
const ld ptod = 1. / dtop;

namespace std {
	bool operator<(const Point &lhs, const Point &rhs) {
		if (lhs.real() < rhs.real() - eps) return true;
		if (lhs.real() > rhs.real() + eps) return false;
		return lhs.imag() < rhs.imag();
	}
}

// 点の入力
Point input_Point() {
	ld x, y;
	cin >> x >> y;
	return Point(x, y);
}

// 誤差つき等号判定
bool eq(const ld a, const ld b) {
	return (abs(a - b) < eps);
}

// 内積
ld dot(const Point& a, const Point& b) {
	return real(conj(a) * b);
}

// 外積
ld cross(const Point& a, const Point& b) {
	return imag(conj(a) * b);
}

// 直線の定義
class Line {
public:
	Point a, b;
	Line() : a(Point(0, 0)), b(Point(0, 0)) {}
	Line(Point a, Point b) : a(a), b(b) {}
	Point operator[](const int _num)const {
		if (_num == 0)return a;
		else if (_num == 1)return b;
		else {
			assert(false);
			return Point();
		}
	}
};

// 円の定義
class Circle {
public:
	Point p;
	ld r;
	Circle() : p(Point(0, 0)), r(0) {}
	Circle(Point p, ld r) : p(p), r(r) {}
};

// ccw
// 1: a,b,cが反時計周りの順に並ぶ
//-1: a,b,cが時計周りの順に並ぶ
// 2: c,a,bの順に直線に並ぶ
//-2: a,b,cの順に直線に並ぶ
// 0: a,c,bの順に直線に並ぶ
int ccw(const Point& a, const Point &b, const Point &c) {
	const Point nb(b - a);
	const Point nc(c - a);
	if (cross(nb, nc) > eps) return 1;   // a,b,cが反時計周りの順に並ぶ
	if (cross(nb, nc) < -eps) return -1; // a,b,cが時計周りの順に並ぶ
	if (dot(nb, nc) < 0) return 2;       // c,a,bの順に直線に並ぶ
	if (norm(nb) < norm(nc)) return -2;  // a,b,cの順に直線に並ぶ
	return 0;                          // a,c,bの順に直線に並ぶ
}


/* 交差判定 */

// 直線と直線の交差判定
bool isis_ll(const Line& l, const Line& m) {
	return !eq(cross(l.b - l.a, m.b - m.a), 0);
}

// 直線と線分の交差判定
bool isis_ls(const Line& l, const Line& s) {
	return isis_ll(l, s) &&
		(cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < eps);
}

// 線分と線分の交差判定
bool isis_ss(const Line& s, const Line& t) {
	return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
		ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

// 点の直線上判定
bool isis_lp(const Line& l, const Point& p) {
	return (abs(cross(l.b - p, l.a - p)) < eps);
}

// 点の線分上判定
bool isis_sp(const Line& s, const Point& p) {
	return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}

// 垂線の足
Point proj(const Line &l, const Point& p) {
	ld t = dot(p - l.a, l.b - l.a) / norm(l.a - l.b);
	return l.a + t * (l.b - l.a);
}

//線対象の位置にある点
Point reflect(const Line &l, const Point &p) {
	Point pr = proj(l, p);
	return pr * 2.l - p;
}

// 直線と直線の交点
Point is_ll(const Line &s, const Line& t) {
	Point sv = s.b - s.a, tv = t.b - t.a;
	assert(cross(sv, tv) != 0);
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
// 直線と直線の交点
vector<Point> is_ll2(const Line &s, const Line& t) {
	Point sv = s.b - s.a, tv = t.b - t.a;
	if (cross(sv, tv) != 0)return vector<Point>(1, is_ll(s, t));
	else {
		vector<Point>ans;
		for (int k = 0; k < 2; ++k) {
			if (isis_sp(s, t[k]) && find(ans.begin(), ans.end(), t[k]) == ans.end())ans.push_back(t[k]);
			if (isis_sp(t, s[k]) && find(ans.begin(), ans.end(), s[k]) == ans.end())ans.push_back(s[k]);
		}
		return ans;
	}
}
// 線分と線分の交点
//　重なってる部分あるとassert(false)
Point is_ss(const Line &s, const Line& t) {
	if (isis_ss(s, t)) {
		for (int k = 0; k < 2; ++k) {
			for (int l = 0; l < 2; ++l) {
				if (s[k] == t[l])return s[k];
			}
		}
		return is_ll(s, t);
	}
	else {
		//先にisis_ssしてね
		assert(false);
		return Point(0, 0);
	}
}
// 線分と線分の交点
vector<Point> is_ss2(const Line &s, const Line& t) {
	vector<Point> kouho(is_ll2(s, t));
	vector<Point>ans;
	for (auto p : kouho) {
		if (isis_sp(s, p) && isis_sp(t, p))ans.emplace_back(p);
	}
	return ans;
}
// 直線と点の距離
ld dist_lp(const Line& l, const Point& p) {
	return abs(p - proj(l, p));
}

//直線と直線の距離
ld dist_ll(const Line& l, const Line& m) {
	return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}

// 直線と線分の距離
ld dist_ls(const Line& l, const Line& s) {
	return isis_ls(l, s) ? 0 : min(dist_lp(l, s.a), dist_lp(l, s.b));
}

// 線分と点の距離
ld dist_sp(const Line& s, const Point& p) {
	Point r = proj(s, p);
	return isis_sp(s, r) ? abs(r - p) : min(abs(s.a - p), abs(s.b - p));
}

// 線分と線分の距離
ld dist_ss(const Line& s, const Line& t) {
	if (isis_ss(s, t)) return 0;
	return min({ dist_sp(s, t.a), dist_sp(s, t.b), dist_sp(t, s.a), dist_sp(t, s.b) });
}


//直線と直線の二等分線のベクトル
Line line_bisection(const Line &s, const Line &t) {
	const Point laglanju(is_ll(s, t));
	const Point avec = !(abs(laglanju - s[0])<eps) ? s[0] - laglanju : s[1] - laglanju;
	const Point bvec = !(abs(laglanju - t[0])<eps) ? t[0] - laglanju : t[1] - laglanju;

	return Line(laglanju, laglanju + (abs(bvec)*avec + abs(avec)*bvec) / (abs(avec) + abs(bvec)));
}
//点と点の垂直二等分線　aを左に見ながら
Line point_bisection(const Point&a, const Point&b) {
	const Point cen((a + b) / 2.l);
	const Point vec = (b - a)*Point(0, 1);
	return Line(cen, cen + vec);
}

//三つの点からなる外心
Point outer_center(const vector<Point>&ps) {
	assert(ps.size() == 3);
	Line l1 = point_bisection(ps[0], ps[1]);
	Line l2 = point_bisection(ps[1], ps[2]);

	return is_ll(l1, l2);
}


//三つの直線からなる内心
//三つの直線が並行でないことは確かめといてね
Point  inner_center(const vector<Line>&ls) {
	vector<Point>vertics;
	for (int i = 0; i <static_cast<int>(ls.size()); ++i) {
		vertics.push_back(is_ll(ls[i], ls[(i + 1) % 3]));
	}
	if (vertics[0] == vertics[1] || vertics[1] == vertics[2] || vertics[2] == vertics[0])return vertics[0];
	Line bi1(line_bisection(Line(vertics[0], vertics[1]), Line(vertics[0], vertics[2])));
	Line bi2(line_bisection(Line(vertics[1], vertics[2]), Line(vertics[1], vertics[0])));
	if (bi1[0] == bi2[0])return bi1[0];
	else {
		return is_ll(bi1, bi2);
	}
}

//三つの直線からなる傍心
//三つの直線が並行でないことは確かめといてね
vector<Point>  ex_center(const vector<Line>&ls) {
	vector<Point>vertics;
	for (int i = 0; i < static_cast<int>(ls.size()); ++i) {
		vertics.push_back(is_ll(ls[i], ls[(i + 1) % 3]));
	}
	if (abs(vertics[0] - vertics[1])<eps || abs(vertics[1] - vertics[2])<eps || (abs(vertics[2] - vertics[0])<eps))return vector<Point>();
	vector<Point>ecs;
	for (int i = 0; i < 3; ++i) {
		Line bi1(line_bisection(Line(vertics[i], vertics[i] * 2.0l - vertics[(i + 2) % 3]), Line(vertics[i], vertics[(i + 1) % 3])));
		Line bi2(line_bisection(Line(vertics[(i + 1) % 3], vertics[(i + 1) % 3] * 2.0l - vertics[(i + 2) % 3]), Line(vertics[(i + 1) % 3], vertics[i])));
		ecs.push_back(is_ll(bi1, bi2));
	}
	return ecs;
}


//a,b:並行
//c:並行でない
//三つの直線から同距離の位置を求める。
vector<Point>  same_dis(const vector<Line>&ls) {
	vector<Point>vertics;
	vertics.push_back(is_ll(ls[0], ls[2]));
	vertics.push_back(is_ll(ls[1], ls[2]));

	if (abs(vertics[0] - vertics[1]) < eps)return vector<Point>{vertics[0]};
	Line bis(line_bisection(ls[0], ls[1]));
	vector<Point>ecs;

	Line abi(line_bisection(Line(vertics[0], vertics[1]), ls[0]));
	ecs.push_back(is_ll(bis, abi));


	Line bbi(line_bisection(Line(vertics[0], 2.l*vertics[0] - vertics[1]), ls[0]));
	ecs.push_back(is_ll(bis, bbi));

	return ecs;
}
/* 円 */

// 円と円の交点
vector<Point> is_cc(const Circle& c1, const Circle& c2) {
	vector<Point> res;
	ld d = abs(c1.p - c2.p);
	ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
	ld dfr = c1.r * c1.r - rc * rc;
	if (abs(dfr) < eps) dfr = 0.0;
	else if (dfr < 0.0) return res; // no intersection
	ld rs = sqrt(dfr);
	Point diff = (c2.p - c1.p) / d;
	res.push_back(c1.p + diff * Point(rc, rs));
	if (dfr != 0.0) res.push_back(c1.p + diff * Point(rc, -rs));
	return res;
}

/*
点が円の中にいるか
0 => out
1 => on
2 => in*/
int is_in_Circle(const  Point& p, const Circle &cir) {
	ld dis = abs(cir.p - p);
	if (dis > cir.r + eps)return 0;
	else if (dis < cir.r - eps)return 2;
	else return 1;
}
int is_in_Circle(const Circle &cir, const  Point& p) {
	ld dis = abs(cir.p - p);
	if (dis > cir.r + eps)return 0;
	else if (dis < cir.r - eps)return 2;
	else return 1;
}
/*
円lcが円rcの中にいるか
0 => out
1 => on
2 => in*/
int Circle_in_Circle(const Circle &lc, const  Circle&rc) {
	ld dis = abs(lc.p - rc.p);
	if (dis < rc.r - lc.r - eps)return 2;
	else if (dis>rc.r - lc.r + eps)return 0;
	else return 1;
}

// 円と直線の交点
vector<Point> is_lc(const Circle& c, const Line& l) {
	vector<Point> res;
	ld d = dist_lp(l, c.p);
	if (d < c.r + eps) {
		ld len = (d > c.r) ? 0.0 : sqrt(c.r * c.r - d * d); //safety;
		Point nor = (l.a - l.b) / abs(l.a - l.b);
		res.push_back(proj(l, c.p) + len * nor);
		res.push_back(proj(l, c.p) - len * nor);
	}
	return res;
}

// 円と線分の距離
vector<Point> is_sc(const Circle& c, const Line& l) {
	vector<Point> v = is_lc(c, l), res;
	for (Point p : v)
		if (isis_sp(l, p)) res.push_back(p);
	return res;
}

// 円と点の接線
vector<Line> tangent_cp(const Circle& c, const Point& p) {
	vector<Line> ret;
	Point v = c.p - p;
	ld d = abs(v);
	ld l = sqrt(norm(v) - c.r * c.r);
	if (isnan(l)) { return ret; }
	Point v1 = v * Point(l / d, c.r / d);
	Point v2 = v * Point(l / d, -c.r / d);
	ret.push_back(Line(p, p + v1));
	if (l < eps) return ret;
	ret.push_back(Line(p, p + v2));
	return ret;
}

// 円と円の接線
vector<Line> tangent_cc(const Circle& c1, const Circle& c2) {
	vector<Line> ret;
	if (abs(c1.p - c2.p) - (c1.r + c2.r) > -eps) {
		Point center = (c1.p * c2.r + c2.p * c1.r) / (c1.r + c2.r);
		ret = tangent_cp(c1, center);
	}
	if (abs(c1.r - c2.r) > eps) {
		Point out = (-c1.p * c2.r + c2.p * c1.r) / (c1.r - c2.r);
		vector<Line> nret = tangent_cp(c1, out);
		ret.insert(ret.end(), nret.begin(), nret.end());
	}
	else {
		Point v = c2.p - c1.p;
		v /= abs(v);
		Point q1 = c1.p + v * Point(0, 1) * c1.r;
		Point q2 = c1.p + v * Point(0, -1) * c1.r;
		ret.push_back(Line(q1, q1 + v));
		ret.push_back(Line(q2, q2 + v));
	}
	return ret;
}
//二つの円の重なり面積
ld two_Circle_area(const Circle&l, const Circle&r) {
	ld dis = abs(l.p - r.p);
	if (dis > l.r + r.r)return 0;
	else if (dis + r.r < l.r) {
		return r.r*r.r*pi;
	}
	else if (dis + l.r < r.r) {
		return l.r*l.r*pi;
	}
	else {
		ld ans = (l.r)*(l.r)*acos((dis*dis + l.r*l.r - r.r*r.r) / (2 * dis*l.r)) +
			(r.r)*(r.r)*acos((dis*dis + r.r*r.r - l.r*l.r) / (2 * dis*r.r)) -
			sqrt(4 * dis*dis*l.r*l.r - (dis*dis + l.r*l.r - r.r*r.r)*(dis*dis + l.r*l.r - r.r*r.r)) / 2;
		return ans;
	}

}

/* 多角形 */

typedef vector<Point> Polygon;



//多角形(複数の点)の最小包含円をO(N=頂点数)で求めるアルゴリズム
//同一直線上に三つの点がないこと
#include<random>
Circle welzl(vector<Point>ps) {
	struct solver {
		Circle solve(vector<Point>&ps, vector<Point>&rs) {
			if (ps.empty() || rs.size() == 3) {
				if (rs.size() == 1) {
					return Circle(Point(rs[0]), 0);
				}
				else if (rs.size() == 2) {
					return Circle((rs[0] + rs[1]) / 2.0l, abs(rs[1] - rs[0]) / 2);
				}
				else if (rs.size() == 3) {
					vector<Line> ls(3);
					for (int i = 0; i < 3; ++i) {
						ls[i] = Line(rs[i], rs[(i + 1) % 3]);
					}
					Point center = outer_center(rs);
					return Circle(center, abs(center - rs[0]));
				}
				else {
					return Circle(Point(), 0);
				}
			}
			else {

				Point p_ba = ps.back();
				ps.pop_back();
				Circle d = solve(ps, rs);
				ps.push_back(p_ba);
				if (is_in_Circle(d, p_ba)) {
					return d;
				}
				else {
					rs.push_back(p_ba);
					ps.pop_back();
					auto ans = solve(ps, rs);
					ps.push_back(p_ba);
					rs.pop_back();
					return ans;
				}
			}
		}
	}so;
	std::random_device rd;
	std::mt19937 mt(rd());
	shuffle(ps.begin(), ps.end(), mt);
	vector<Point>rs;
	Circle ans = so.solve(ps, rs);
	return ans;
}
// 面積
ld get_area(const Polygon &p) {
	ld res = 0;
	int n = p.size();
	for (int j = 0; j<n; ++j) res += cross(p[j], p[(j + 1) % n]);
	return res / 2;
}

//多角形の回転方向
bool is_counter_clockwise(const Polygon &poly) {
	ld angle = 0;
	int n = poly.size();
	for(int i=0;i<n;++i) {
		Point a = poly[i], b = poly[(i + 1) % n], c = poly[(i + 2) % n];
		angle += arg((c - b) / (b - a));
	}
	return angle > eps;
}

// 円の内外判定
/*0 => out
1 => on
2 => in*/
int is_in_Polygon(const Polygon &poly, const  Point& p) {
	ld angle = 0;
	int n = poly.size();
	for(int i=0;i<n;++i) {
		Point a = poly[i], b = poly[(i + 1) % n];
		if (isis_sp(Line(a, b), p)) return 1;
		angle += arg((b - p) / (a - p));
	}
	return eq(angle, 0) ? 0 : 2;
}
//円の内外判定2　高速
enum { out, on, in };
int convex_contains(const Polygon &P, const Point &p) {
	const int n = P.size();
	Point g = (P[0] + P[n / 3] + P[2 * n / 3]) / 3.0l; // inner-point
	int a = 0, b = n;
	while (a + 1 < b) { // invariant: c is in fan g-P[a]-P[b]
		int c = (a + b) / 2;
		if (cross(P[a] - g, P[c] - g) > 0) { // angle < 180 deg
			if (cross(P[a] - g, p - g) > 0 && cross(P[c] - g, p - g) < 0) b = c;
			else                                                  a = c;
		}
		else {
			if (cross(P[a] - g, p - g) < 0 && cross(P[c] - g, p - g) > 0) a = c;
			else                                                  b = c;
		}
	}
	b %= n;
	if (cross(P[a] - p, P[b] - p) < 0) return 0;
	if (cross(P[a] - p, P[b] - p) > 0) return 2;
	return 1;
}

// 凸包
//点や線を返すことも有り得るので注意
Polygon convex_hull(vector<Point> ps) {
	int n = ps.size();
	int k = 0;
	sort(ps.begin(), ps.end());
	Polygon ch(2 * n);
	for (int i = 0; i < n; ch[k++] = ps[i++])
		while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--])
		while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	ch.resize(k - 1);
	return ch;
}



//凸カット
vector<Polygon> convex_cut(const Polygon &ps, const Line& l) {
	int n = ps.size();
	Polygon q;
	Polygon r;
	for(int i=0;i<n;++i) {
		Point a = ps[i], b = ps[(i + 1) % n];
		Line m = Line(a, b);
		if (ccw(l.a, l.b, a) != -1) q.push_back(a);
		if (ccw(l.a, l.b, a) != 1) r.push_back(a);
		if (ccw(l.a, l.b, a) * ccw(l.a, l.b, b) < 0 && isis_ll(l, m)) {
			q.push_back(is_ll(l, m));
			r.push_back(is_ll(l, m));
		}
	}
	const vector<Polygon>polys{ q,r };
	return polys;
}


/* アレンジメント */
void add_Point(vector<Point> &ps, const Point p) {
	for (Point q : ps) if (abs(q - p) < eps) return;
	ps.push_back(p);
}

bool solve(vector<pair<ld, vector<int>>>bombs, int N, int M, ld len) {
	{
		auto n_bombs(bombs);
		n_bombs.clear();
		for (int i = 0; i < bombs.size(); ++i) {
			ld r=bombs[i].first;
			if(r<len)n_bombs.emplace_back(bombs[i]);
		}
		bombs=n_bombs;
	}

	vector<vector<int>>memo(M+1,vector<int>(1<<N));
	memo[0][0]=true;
	for (int b_use = 0; b_use < M; ++b_use) {
		for (int i = 0; i < (1 << N); ++i) {
			if(!memo[b_use][i])continue;

			for (auto&& now_b : bombs) {

				bitset<14>bs(i);
				for (int j = 0; j < N; ++j) {
					if(now_b.second[j])bs[j]=true;
				}
				memo[b_use+1][bs.to_ulong()]=true;
			}
		}
	}
	return memo[M][(1<<N)-1];
}



int main() {
	int N,M;cin>>N>>M;
	vector<Point>pos;
	for (int i = 0; i < N; ++i) {
		int x,y;cin>>x>>y;
		pos.push_back(Point(x,y));
	}

	vector<pair<ld,vector<int>>>bombs;
	{
		vector<int>v(3);
		for (v[0] = 0; v[0] < N; ++v[0]) {
			{
				ld r=1e-8;
				Circle c(pos[v[0]], r);

				vector<int>oks(N);
				for (int i = 0; i < N; ++i) {
					if (is_in_Circle(c, pos[i])) {
						oks[i] = true;
					}
				}
				bombs.push_back(make_pair(r, oks));
			}
			for ( v[1] = v[0] + 1; v[1] < N; ++v[1]) {
				{
					Point p((pos[v[0]]+pos[v[1]])/2.0l);
					const ld r = abs(p - pos[v[0]]);
					Circle c(p, r);

					vector<int>oks(N);
					for (int i = 0; i < N; ++i) {
						if (is_in_Circle(c, pos[i])) {
							oks[i] = true;
						}
					}
					bombs.push_back(make_pair(r, oks));
				}
				
				for (v[2] = v[1] + 1; v[2] < N; ++v[2]) {
					vector<Point>ci_pos(3);
					for (int i = 0; i < 3; ++i) {
						ci_pos[i]=pos[v[i]];
					}
					Line l1 = point_bisection(ci_pos[0], ci_pos[1]);
					Line l2 = point_bisection(ci_pos[1], ci_pos[2]);
					Point sv = l1.b - l1.a, tv = l2.b - l2.a;
					if (abs(cross(sv, tv)) < eps) {
						continue;
					}

					Point p(outer_center(ci_pos));
					const ld r=abs(p-ci_pos[0]);
					Circle c(p,r);

					vector<int>oks(N);
					for (int i = 0; i < N; ++i) {
						if (is_in_Circle(c, pos[i])) {
							oks[i]=true;
						}
					}
					bombs.push_back(make_pair(r,oks));
				}
			}
		}
	}
	{
		map<int, ld>mp;
		for (auto&& bomb : bombs) {
			bitset<14>bs;
			for (int i = 0; i < bomb.second.size(); ++i) {
				if(bomb.second[i])bs[i]=true;
			}
			if (mp.find(bs.to_ulong()) == mp.end()) {
				mp[bs.to_ulong()]=bomb.first;
			}
			else {
				mp[bs.to_ulong()]=min(bomb.first,mp[bs.to_ulong()]);
			}
		}
		auto n_bombs(bombs);
		n_bombs.clear();
		for (auto m : mp) {
			bitset<14>bs(m.first);
			vector<int>v(N);
			for (int i = 0; i < N; ++i) {
				if(bs[i])v[i]=true;
			}
			n_bombs.emplace_back(m.second,v);
		}
		bombs=n_bombs;
	}

	ld l=0,r=1e5;
	int time=30;
	while (time--) {
		ld m=(l+r)/2;
		if (solve(bombs, N, M, m)) {
			r=m;
		}
		else {
			l=m;
		}
	}
	cout<<setprecision(10)<<fixed;
	cout<<l<<endl;
	return 0;
}