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>
using namespace std;

using ld = double;
using P = std::complex<ld>;
using G = std::vector<P>;
const ld pi = std::acos(-1);
const ld eps = 1e-10;
const ld inf = 1e12;

ld cross(const P &a, const P &b) { return a.real() * b.imag() - a.imag() * b.real(); }
ld dot(const P &a, const P &b) { return a.real() * b.real() + a.imag() * b.imag(); }

/*
                    CCW

 -- BEHIND -- [a -- ON -- b] --- FRONT --

                    CW
 */
enum CCW_RESULT { CCW = +1, CW = -1, BEHIND = +2, FRONT = -2, ON = 0 };
int ccw(P a, P b, P c) {
    b -= a;
    c -= a;
    if (cross(b, c) > eps) return CCW;    // counter clockwise
    if (cross(b, c) < -eps) return CW;    // clockwise
    if (dot(b, c) < 0) return BEHIND;     // c--a--b on line
    if (norm(b) < norm(c)) return FRONT;  // a--b--c on line
    return ON;
}

namespace std {
    bool operator<(const P &a, const P &b) {
        return std::abs(real(a) - real(b)) > eps ? real(a) < real(b) : imag(a) < imag(b);
    }
}

struct L : public std::vector<P> {
    L(const P &a = P(), const P &b = P()) : std::vector<P>(2) {
        begin()[0] = a;
        begin()[1] = b;
    }

    // Ax + By + C = 0
    L(ld A, ld B, ld C) {
        if (std::abs(A) < eps && std::abs(B) < eps) {
            abort();
        } else if (std::abs(A) < eps) {
            *this = L(P(0, -C / B), P(1, -C / B));
        } else if (std::abs(B) < eps) {
            *this = L(P(-C / A, 0), P(-C / A, 1));
        } else {
            *this = L(P(0, -C / B), P(-C / A, 0));
        }
    }
};

struct C {
    P p;
    ld r;
    C(const P &p = 0, ld r = 0) : p(p), r(r) {}
};


template <class iter>
std::pair<P, ld> min_ball(iter left, iter right) {
    int n = right - left;
    assert(n >= 1);
    if (n == 1) {
        return {*left, ld(0)};
    }

    random_shuffle(left, right);
    iter ps = left;
    using circle = std::pair<P, ld>;
    auto make_circle_3 = [](const P &a, const P &b, const P &c) -> circle {
        ld A = std::norm(b - c), B = std::norm(c - a), C = std::norm(a - b),
           S = cross(b - a, c - a);
        P p = (A * (B + C - A) * a + B * (C + A - B) * b + C * (A + B - C) * c) / (4 * S * S);
        ld r2 = std::norm(p - a);
        return {p, r2};
    };

    auto make_circle_2 = [](const P &a, const P &b) -> circle {
        P c = (a + b) / (ld)2;
        ld r2 = std::norm(a - c);
        return {c, r2};
    };

    auto in_circle = [](const P &a, const circle &c) -> bool {
        return std::norm(a - c.first) <= c.second + eps;
    };

    circle c = make_circle_2(ps[0], ps[1]);
    n = right - left;
    // MiniDisc
    for (int i = 2; i < n; ++i) {
        if (!in_circle(ps[i], c)) {
            // MiniDiscWithPoint
            c = make_circle_2(ps[0], ps[i]);
            for (int j = 1; j < i; ++j) {
                if (!in_circle(ps[j], c)) {
                    // MiniDiscWith2Points
                    c = make_circle_2(ps[i], ps[j]);
                    for (int k = 0; k < j; ++k) {
                        if (!in_circle(ps[k], c)) {
                            c = make_circle_3(ps[i], ps[j], ps[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}

int main() {
    int n, m;
    cin >> n >> m;
    if (n == m) {
        cout << "0\n";
        return 0;
    }
    G p(n);
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        p[i] = P(x, y);
    }
    vector<ld> r(1 << n);
    set<ld> rs;
    rs.insert(0);
    for (int i = 1; i < (1 << n); ++i) {
        G pt;
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                pt.push_back(p[j]);
            }
        }
        if (pt.size() <= 1) {
            r[i] = 0;
        }
        else {
            r[i] = sqrt(min_ball(pt.begin(), pt.end()).second);
            rs.insert(r[i]);
        }
    }
    vector<ld> rv;
    rv.push_back(-1e-9);
    for (ld i : rs) {
        rv.push_back(i + 1e-9);
    }
    rv.push_back(r[(1 << n) - 1] + 1e-9);
    int ng = 0, ok = (int)rv.size() - 1;
    while (ok > ng + 1) {
        int mid = (ok + ng) / 2;
        ld rm = rv[mid];
        vector<int> dp(1 << n, n);
        dp[0] = 0;
        vector<int> pl;
        for (int i = 1; i < (1 << n); ++i) {
            if (r[i] < rm) {
                pl.push_back(i);
            }
        }
        for (int i = 1; i < (1 << n); ++i) {
            for (int j : pl) {
                dp[i] = min(dp[i], dp[i & ~j] + 1);
            }
        }
        if (dp[(1 << n) - 1] <= m) {
            ok = mid;
        }
        else {
            ng = mid;
        }
    }
    printf("%.9lf\n", rv[ok]);
    return 0;
}