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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define ld long double

using namespace std;

const ld eps = 1e-9;

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

struct Point
{
    ld x;
    ld y;
};

struct Circle : Point
{
    Circle(ld x, ld y, ld r) : Point{x, y}, r(r) {}
    ld r;
};

ld dist(Point &p1, Point &p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

vector<Point> intersection(Circle c1, Circle c2)
{
    ld d = dist(c1, c2);
    if (d > c1.r + c2.r || d < abs(c1.r - c2.r))
        return {};
    ld a = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
    ld h = sqrt(c1.r * c1.r - a * a);
    ld xm = c1.x + a * (c2.x - c1.x) / d;
    ld ym = c1.y + a * (c2.y - c1.y) / d;
    return {{xm - h / d * (c2.y - c1.y), ym + h / d * (c2.x - c1.x)},
            {xm + h / d * (c2.y - c1.y), ym - h / d * (c2.x - c1.x)}};
}

bool inCircle(Circle c, Point p)
{
    return dist(c, p) <= c.r + eps;
}

int n, k;
vector<Circle> cs;

int cooked(ld t)
{
    int mx1 = 0;
    for (int i = 0; i < cs.size() - 1; i++)
    {
        for (int j = i + 1; j < cs.size(); j++)
        {
            auto ps = intersection({cs[i].x, cs[i].y, cs[i].r * t}, {cs[j].x, cs[j].y, cs[j].r * t});
            for (auto &p : ps)
            {
                int count = 0;
                for (int ci = 0; ci < cs.size(); ci++)
                {
                    if (inCircle({cs[ci].x, cs[ci].y, cs[ci].r * t}, p))
                    {
                        count++;
                    }
                }
                mx1 = max(mx1, count);
            }
        }
    }
    int mx2 = 0;
    for (int i = 0; i < cs.size(); i++)
    {
        int count = 0;
        for (int j = 0; j < cs.size(); j++)
        {
            if (inCircle({cs[j].x, cs[j].y, cs[j].r * t}, cs[i]))
                count++;
        }
        mx2 = max(mx2, count);
    }
    return max(mx1, mx2);
}

ld bin_search(ld tl, ld th)
{
    ld mid = (tl + th) / 2;
    if (th - tl < 1e-6)
        return mid;
    if (cooked(mid) >= k)
        return bin_search(tl, mid);
    else
        return bin_search(mid, th);
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        ld x, y, c;
        cin >> x >> y >> c;
        Circle ci{x, y, 1 / c};
        cs.push_back(ci);
    }

    cout << fixed << bin_search(0, 1e6) << endl;
    return 0;
}