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 <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

struct point { double x, y; };
int n, k, EPS = 100;
double l = 0, ri = 1E10;
vector<point> p;
vector<double> c;

double len(point a, point b) { return hypot((a.x - b.x), (a.y - b.y)); }

bool yet_ok(double t)
{
    if (n == 1)
        return true;

     vector<double> r(n);

    for (int i = 0; i < n; i++)
        r[i] = t / c[i];

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            if (len(p[i], p[j]) > r[i] + r[j])
                continue;

            if (len(p[i], p[j]) < fabs(r[i] - r[j]))
                continue;

            double a1 = -2 * (p[i].x - p[j].x);
            double b1 = -2 * (p[i].y - p[j].y);
            double c1 = p[i].x * p[i].x - p[j].x * p[j].x + p[i].y * p[i].y -
                    p[j].y * p[j].y - r[i] * r[i] + r[j] * r[j];

            point o;
            int cnt = 0;

            double d1 = len({ 0, 0 }, { a1, b1 });
            a1 /= d1;
            b1 /= d1;
            c1 /= d1;

            d1 = a1 * p[i].x + b1 * p[i].y + c1;

            o = { p[i].x - a1 * d1, p[i].y - b1 * d1};
            double move = sqrt(r[i] * r[i] - d1 * d1);

            vector<point> all_dots = {
                    {o.x + b1 * move, o.y - a1 * move},
                    {o.x - b1 * move, o.y + a1 * move}
            };

            for (auto v : all_dots)
            {
                cnt = 0;
                o = v;
                for (int q = 0; q < n; q++)
                    if (len(p[q], o) <= r[q] || q == i || q == j)
                        cnt++;

                if (cnt >= k)
                    return true;
            }
        }

    for (auto o : p)
    {
        int cnt = 0;
        for (int q = 0; q < n; q++)
            if (len(p[q], o) <= r[q])
                cnt++;

        if (cnt >= k)
            return true;
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    p.resize(n);
    c.resize(n);

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

    for (int it = 0; it < EPS; it++)
    {
        double m = (l + ri) / 2;

        if (yet_ok(m))
            ri = m;
        else
            l = m;
    }

    cout << fixed << setprecision(20);
    cout << ri << "\n";

    return 0;
}