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 long long long int
using namespace std;

// @author: pashka

struct point {
    double x, y;
};

double dist(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int n, k;
vector<point> p;
vector<double> c;

bool good(double t) {
    if (k == 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 (dist(p[i], p[j]) > r[i] + r[j]) continue;
            if (dist(p[i], p[j]) < abs(r[i] - r[j])) continue;
            double aa = -2 * (p[i].x - p[j].x);
            double bb = -2 * (p[i].y - p[j].y);
            double cc = 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];
            // aa * x + bb * y + cc = 0
            double dd = dist({0, 0}, {aa, bb});
            aa /= dd;
            bb /= dd;
            cc /= dd;

            dd = aa * p[i].x + bb * p[i].y + cc;
            point perp = {p[i].x - aa * dd, p[i].y - bb * dd};
            double qq = sqrt(r[i] * r[i] - dd * dd);

            vector<point> oo = {
                    {perp.x + bb * qq, perp.y - aa * qq},
                    {perp.x - bb * qq, perp.y + aa * qq}
            };

            for (point o : oo) {
                int s = 0;
                for (int q = 0; q < n; q++) {
                    if (dist(p[q], o) <= r[q] || q == i || q == j) s++;
                }
                if (s >= k) return true;
            }
        }
    }
    for (point o : p) {
        int s = 0;
        for (int q = 0; q < n; q++) {
            if (dist(p[q], o) <= r[q]) s++;
        }
        if (s >= k) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);

    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];
    }

    double l = 0;
    double r = 1e10;
    for (int tt = 0; tt < 100; tt++) {
        double m = (l + r) / 2;
        if (good(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << setprecision(20) << r << "\n";

    return 0;
}