#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double ld;
const int MAXN = 65;
const double EPS = 1e-7;

struct pt
{
    double x, y;

    pt()
    {
        x = 0;
        y = 0;
    }

    pt (double __x, double __y)
    {
        x = __x;
        y = __y;
    }

    pt add (pt p)
    {
        return pt(x + p.x, y + p.y);
    }

    pt sub (pt p)
    {
        return pt(x - p.x, y - p.y);
    }

    double dist()
    {
        return sqrt (x * x + y * y);
    }

    pt norm()
    {
        double d = sqrt (x * x + y * y);
        return pt(x / d, y / d);
    }

    pt mult (double d)
    {
        return pt(x * d, y * d);
    }

    pt rot()
    {
        return pt(-y, x);
    }
};

int N, K;
double c[MAXN];
pt p[MAXN];
double r[MAXN];

bool okay (pt goal)
{
    int ans = 0;
    for (int i = 0; i < N; i++)
        if (goal.sub(p[i]).dist() < r[i] + EPS)
            ans++;
    return ans >= K;
}

bool works (ld t)
{
    for (int i = 0; i < N; i++)
        r[i] = t / c[i];

    for (int i = 0; i < N; i++)
        if (okay (p[i]))
            return true;

    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
        {
            double dv = p[i].sub(p[j]).dist();
            if (dv - EPS < abs (r[i] - r[j])) continue;
            if (dv + EPS > r[i] + r[j]) continue;

            double nv = r[i] * r[i] - r[j] * r[j];
            double pv = nv / dv;
            double av = (dv + pv) / 2;

            pt dir = p[j].sub(p[i]).norm();
            pt pg = p[i].add(dir.mult(av));

            double ov = sqrt (r[i] * r[i] - av * av);
            pt pdone1 = pg.add(dir.rot().mult(ov));
            pt pdone2 = pg.add(dir.rot().mult(-ov));
            if (okay (pdone1) || okay (pdone2))
                return true;
        }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> p[i].x >> p[i].y >> c[i];

    if (K == 1)
    {
        cout << "0.0\n";
        return 0;
    }

    ld lo = 0., hi = 1e6;
    for (int i = 0; i < 50; i++)
    {
        ld mid = (lo + hi) / 2;
        if (works (mid))
            hi = mid;
        else
            lo = mid;
    }

    cout << fixed << setprecision(8);
    cout << lo << "\n";
}
### 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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double ld;
const int MAXN = 65;
const double EPS = 1e-7;

struct pt
{
    double x, y;

    pt()
    {
        x = 0;
        y = 0;
    }

    pt (double __x, double __y)
    {
        x = __x;
        y = __y;
    }

    pt add (pt p)
    {
        return pt(x + p.x, y + p.y);
    }

    pt sub (pt p)
    {
        return pt(x - p.x, y - p.y);
    }

    double dist()
    {
        return sqrt (x * x + y * y);
    }

    pt norm()
    {
        double d = sqrt (x * x + y * y);
        return pt(x / d, y / d);
    }

    pt mult (double d)
    {
        return pt(x * d, y * d);
    }

    pt rot()
    {
        return pt(-y, x);
    }
};

int N, K;
double c[MAXN];
pt p[MAXN];
double r[MAXN];

bool okay (pt goal)
{
    int ans = 0;
    for (int i = 0; i < N; i++)
        if (goal.sub(p[i]).dist() < r[i] + EPS)
            ans++;
    return ans >= K;
}

bool works (ld t)
{
    for (int i = 0; i < N; i++)
        r[i] = t / c[i];

    for (int i = 0; i < N; i++)
        if (okay (p[i]))
            return true;

    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
        {
            double dv = p[i].sub(p[j]).dist();
            if (dv - EPS < abs (r[i] - r[j])) continue;
            if (dv + EPS > r[i] + r[j]) continue;

            double nv = r[i] * r[i] - r[j] * r[j];
            double pv = nv / dv;
            double av = (dv + pv) / 2;

            pt dir = p[j].sub(p[i]).norm();
            pt pg = p[i].add(dir.mult(av));

            double ov = sqrt (r[i] * r[i] - av * av);
            pt pdone1 = pg.add(dir.rot().mult(ov));
            pt pdone2 = pg.add(dir.rot().mult(-ov));
            if (okay (pdone1) || okay (pdone2))
                return true;
        }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> p[i].x >> p[i].y >> c[i];

    if (K == 1)
    {
        cout << "0.0\n";
        return 0;
    }

    ld lo = 0., hi = 1e6;
    for (int i = 0; i < 50; i++)
    {
        ld mid = (lo + hi) / 2;
        if (works (mid))
            hi = mid;
        else
            lo = mid;
    }

    cout << fixed << setprecision(8);
    cout << lo << "\n";
}
```