// https://atcoder.jp/contests/abc157/tasks/abc157_f
#include <bits/stdc++.h>
using namespace std;

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n-1);i>=0;i--)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

const double EPS = 1e-9;
#define le(a,b) ((a) < (b) - EPS)      // <
#define gr(a,b) ((a) > (b) + EPS)      // >
#define leq(a,b) ((a) < (b) + EPS)     // <=
#define geq(a,b) ((a) > (b) - EPS)     // >=
#define eq(a,b) (abs((a) - (b)) < EPS) // ==

struct pto {
	double x, y;
	pto(double _x=0, double _y=0) : x(_x),y(_y) {}
	pto operator+(pto a) { return pto(x + a.x, y + a.y); }
	pto operator-(pto a) { return pto(x - a.x, y - a.y); }
	pto operator*(double a) { return pto(x*a, y*a); }
	pto operator/(double a) { return pto(x/a, y/a); }
	double norm() { return sqrt(x*x + y*y); }
};
double dist(pto a, pto b) { return (b-a).norm(); }
pto CCW90(pto p) { return pto(-p.y, p.x); }

struct circle { 
    pto p; double r; 
    bool contains(pto &a) { return leq(dist(p, a), r); }
};

vector<pto> interCC(circle &a, circle &b) {
    vector<pto> r;
    double d = dist(a.p, b.p);
    if (gr(d, a.r + b.r) || le(d + min(a.r, b.r), max(a.r, b.r))) return r;
    double x = (d*d + a.r*a.r - b.r*b.r) / (2*d);
    double y = sqrt(a.r*a.r - x*x);
    pto v = (b.p - a.p) / d;
    r.pb(a.p + v*x + CCW90(v)*y);
    if (gr(y, 0)) r.pb(a.p + v*x - CCW90(v)*y);
    return r;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int n,k; cin >> n >> k;
    vector<pto> a(n); 
    int b[n];
    forn(i, n) cin >> a[i].x >> a[i].y >> b[i];

    auto f = [&](double t) { // O(n^3)
        vector<circle> cir(n);
        forn(i, n) cir[i] = {a[i], t/b[i]};

        vector<pto> can(all(a));
        forn(i, n) forsn(j, i+1, n)
            for (pto &p : interCC(cir[i], cir[j])) 
                can.pb(p);

        int m = 0;
        for (auto &p : can) {
            int q = 0;
            for (auto &c : cir)
                if (c.contains(p)) q++;
            m = max(m, q);
        }
        return m < k;
    };

    double l = 0, h = 3e5;
    while (!eq(l, h)) {
        double m = (l+h)/2;
        if (f(m)) l = m;
        else h = m;
    }
    cout << fixed << setprecision(6) << h << endl;
    return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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
// https://atcoder.jp/contests/abc157/tasks/abc157_f
#include <bits/stdc++.h>
using namespace std;

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n-1);i>=0;i--)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

const double EPS = 1e-9;
#define le(a,b) ((a) < (b) - EPS)      // <
#define gr(a,b) ((a) > (b) + EPS)      // >
#define leq(a,b) ((a) < (b) + EPS)     // <=
#define geq(a,b) ((a) > (b) - EPS)     // >=
#define eq(a,b) (abs((a) - (b)) < EPS) // ==

struct pto {
	double x, y;
	pto(double _x=0, double _y=0) : x(_x),y(_y) {}
	pto operator+(pto a) { return pto(x + a.x, y + a.y); }
	pto operator-(pto a) { return pto(x - a.x, y - a.y); }
	pto operator*(double a) { return pto(x*a, y*a); }
	pto operator/(double a) { return pto(x/a, y/a); }
	double norm() { return sqrt(x*x + y*y); }
};
double dist(pto a, pto b) { return (b-a).norm(); }
pto CCW90(pto p) { return pto(-p.y, p.x); }

struct circle { 
    pto p; double r; 
    bool contains(pto &a) { return leq(dist(p, a), r); }
};

vector<pto> interCC(circle &a, circle &b) {
    vector<pto> r;
    double d = dist(a.p, b.p);
    if (gr(d, a.r + b.r) || le(d + min(a.r, b.r), max(a.r, b.r))) return r;
    double x = (d*d + a.r*a.r - b.r*b.r) / (2*d);
    double y = sqrt(a.r*a.r - x*x);
    pto v = (b.p - a.p) / d;
    r.pb(a.p + v*x + CCW90(v)*y);
    if (gr(y, 0)) r.pb(a.p + v*x - CCW90(v)*y);
    return r;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int n,k; cin >> n >> k;
    vector<pto> a(n); 
    int b[n];
    forn(i, n) cin >> a[i].x >> a[i].y >> b[i];

    auto f = [&](double t) { // O(n^3)
        vector<circle> cir(n);
        forn(i, n) cir[i] = {a[i], t/b[i]};

        vector<pto> can(all(a));
        forn(i, n) forsn(j, i+1, n)
            for (pto &p : interCC(cir[i], cir[j])) 
                can.pb(p);

        int m = 0;
        for (auto &p : can) {
            int q = 0;
            for (auto &c : cir)
                if (c.contains(p)) q++;
            m = max(m, q);
        }
        return m < k;
    };

    double l = 0, h = 3e5;
    while (!eq(l, h)) {
        double m = (l+h)/2;
        if (f(m)) l = m;
        else h = m;
    }
    cout << fixed << setprecision(6) << h << endl;
    return 0;
}

```