#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;
const double eps = 1E-9;

bool equal (double a, double b)
{
    return abs(a-b)<eps;
}

struct V {
    double x, y;
    V(double x=0, double y=0): x(x), y(y) {}
    V operator+(const V& p) const { return V(x+p.x, y+p.y); }
    V operator-(const V& p) const { return V(x-p.x, y-p.y); }
    V operator*(double a) const { return V(x*a, y*a); }
    double sqrNorm() const { return x*x+y*y; }
    double norm() const { return sqrt(sqrNorm()); }
    V rotate90() const { return V(-y, x); }
};

struct Circle {
    V o;
    double r;
    Circle(V o=V(), double r=0): o(o), r(r) {}
    vector<V> xp(const Circle& c) {
        V v = c.o-o;
        double l = v.norm();
        double sub = abs(r-c.r);
        double add = r+c.r;
        if (equal(l, sub)) {
            if (r>c.r) return {o+v*(r/l)};
            else return {o+v*(-r/l)};
        }
        if (equal(l, add)) {
            return {o+v*(r/l)};
        }
        if (l>add || l<sub) {
            return {};
        }
        double x = (r*r-c.r*c.r+l*l)/(2.0*l);
        V mid = o+v*(x/l);
        V dx = v.rotate90()*((sqrt(r*r-x*x))/l);
        return {mid+dx, mid-dx};
    }
    bool isInside(const V& p) {
        return (p-o).norm() < r+eps;
    }
};

int main(){
    int n, k;
    cin >> n >> k;
    vector<Circle> cir(n);
    rep(i, n) {
        int x, y, c;
        cin >> x >> y >> c;
        cir[i] = Circle(V(x, y), c);
    }
    
    double l = 0.0;
    double r = 4000000.0;
    rep(ti, 100) {
        double t = 0.5*(l+r);
        vector<V> ps;
        rep(i, n) {
            ps.push_back(cir[i].o);
        }
        rep(i, n) rep(j, i) {
            Circle a = cir[i];
            Circle b = cir[j];
            a.r = t/a.r;
            b.r = t/b.r;
            vector<V> temp = a.xp(b);
            for (V v:temp) {
                ps.push_back(v);
            }
        }
        bool ok = false;
        for (V v:ps) {
            int cnt = 0;
            rep(i, n) {
                Circle a = cir[i];
                a.r = t/a.r;
                if (a.isInside(v)) cnt++;
            }
            if (cnt>=k) ok = true;
        }
        if (ok) r = t;
        else l = t;
    }
    printf("%.10f\n", r);
    
    
    
    return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

Takahashi wants to grill N pieces of meat on a grilling net, which can be seen as a two-dimensional plane. The coordinates of the i-th piece of meat are \left(x_i, y_i\right), and its hardness is c_i.

Takahashi can use one heat source to grill the meat. If he puts the heat source at coordinates \left(X, Y\right), where X and Y are real numbers, the i-th piece of meat will be ready to eat in c_i \times \sqrt{\left(X - x_i\right)^2 + \left(Y-y_i\right)^2} seconds.

Takahashi wants to eat K pieces of meat. Find the time required to have K or more pieces of meat ready if he put the heat source to minimize this time.

Constraints

* All values in input are integers.
* 1 \leq N \leq 60
* 1 \leq K \leq N
* -1000 \leq x_i , y_i \leq 1000
* \left(x_i, y_i\right) \neq \left(x_j, y_j\right) \left(i \neq j \right)
* 1 \leq c_i \leq 100

Input

Input is given from Standard Input in the following format:


N K
x_1 y_1 c_1
\vdots
x_N y_N c_N


Output

Print the answer.

It will be considered correct if its absolute or relative error from our answer is at most 10^{-6}.

Examples

Input

4 3
-1 0 3
0 0 3
1 0 2
1 1 40


Output

2.4


Input

10 5
-879 981 26
890 -406 81
512 859 97
362 -955 25
128 553 17
-885 763 2
449 310 57
-656 -204 11
-270 76 40
184 170 16


Output

7411.2252

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;
const double eps = 1E-9;

bool equal (double a, double b)
{
    return abs(a-b)<eps;
}

struct V {
    double x, y;
    V(double x=0, double y=0): x(x), y(y) {}
    V operator+(const V& p) const { return V(x+p.x, y+p.y); }
    V operator-(const V& p) const { return V(x-p.x, y-p.y); }
    V operator*(double a) const { return V(x*a, y*a); }
    double sqrNorm() const { return x*x+y*y; }
    double norm() const { return sqrt(sqrNorm()); }
    V rotate90() const { return V(-y, x); }
};

struct Circle {
    V o;
    double r;
    Circle(V o=V(), double r=0): o(o), r(r) {}
    vector<V> xp(const Circle& c) {
        V v = c.o-o;
        double l = v.norm();
        double sub = abs(r-c.r);
        double add = r+c.r;
        if (equal(l, sub)) {
            if (r>c.r) return {o+v*(r/l)};
            else return {o+v*(-r/l)};
        }
        if (equal(l, add)) {
            return {o+v*(r/l)};
        }
        if (l>add || l<sub) {
            return {};
        }
        double x = (r*r-c.r*c.r+l*l)/(2.0*l);
        V mid = o+v*(x/l);
        V dx = v.rotate90()*((sqrt(r*r-x*x))/l);
        return {mid+dx, mid-dx};
    }
    bool isInside(const V& p) {
        return (p-o).norm() < r+eps;
    }
};

int main(){
    int n, k;
    cin >> n >> k;
    vector<Circle> cir(n);
    rep(i, n) {
        int x, y, c;
        cin >> x >> y >> c;
        cir[i] = Circle(V(x, y), c);
    }
    
    double l = 0.0;
    double r = 4000000.0;
    rep(ti, 100) {
        double t = 0.5*(l+r);
        vector<V> ps;
        rep(i, n) {
            ps.push_back(cir[i].o);
        }
        rep(i, n) rep(j, i) {
            Circle a = cir[i];
            Circle b = cir[j];
            a.r = t/a.r;
            b.r = t/b.r;
            vector<V> temp = a.xp(b);
            for (V v:temp) {
                ps.push_back(v);
            }
        }
        bool ok = false;
        for (V v:ps) {
            int cnt = 0;
            rep(i, n) {
                Circle a = cir[i];
                a.r = t/a.r;
                if (a.isInside(v)) cnt++;
            }
            if (cnt>=k) ok = true;
        }
        if (ok) r = t;
        else l = t;
    }
    printf("%.10f\n", r);
    
    
    
    return 0;
}

```