#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;
using ld = long double;

struct point {
    ld x, y, c;
};

using vp = vector<point>;

const int M = 50;
const ld EPS = 1e-12;

ld dis(point a, point b) {
    ld dx = a.x - b.x;
    ld dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

vp cyc_intersec(point a, point b) {
    ld d = dis(a, b);
    if (d > a.c + b.c + EPS || d < abs(a.c - b.c) - EPS) {
        return {};
    }

    ld p = acos(max(-1.0l, min(1.0l, (a.c * a.c + d * d - b.c * b.c) / (2 * a.c * d))));
    ld t = atan2(b.y - a.y, b.x - a.x);

    point p1, p2;
    p1.x = a.x + a.c * cos(t + p);
    p1.y = a.y + a.c * sin(t + p);
    p2.x = a.x + a.c * cos(t - p);
    p2.y = a.y + a.c * sin(t - p);

    return {p1, p2};
}

int calc(point x, const vp &cyc) {
    int r = 0;
    for (point y : cyc) {
        if (dis(x, y) < y.c + EPS) {
            r++;
        }
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vp p(n);
    for (int i = 0; i < n; i++) {
        cin >> p.at(i).x >> p.at(i).y >> p.at(i).c;
    }

    if (k == 1) {
        cout << 0 << endl;
        return 0;
    }

    ld l = 0, r = 2e5;
    for (int q = 0; q < M; q++) {
        ld mid = (l + r) / 2;

        vp cyc(n);
        for (int i = 0; i < n; i++) {
            cyc.at(i).x = p.at(i).x;
            cyc.at(i).y = p.at(i).y;
            cyc.at(i).c = mid / p.at(i).c;
        }

        bool f = false;

        for (point x : p) {
            if (calc(x, cyc) >= k) {
                f = true;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                vp t = cyc_intersec(cyc.at(i), cyc.at(j));
                for (point x : t) {
                    if (calc(x, cyc) >= k) {
                        f = true;
                    }
                }
            }
        }

        if (f) {
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << fixed << setprecision(7) << r << endl;

    return 0;
}

### Prompt

Please formulate a Cpp solution to the following 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

### Response

```cpp
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;
using ld = long double;

struct point {
    ld x, y, c;
};

using vp = vector<point>;

const int M = 50;
const ld EPS = 1e-12;

ld dis(point a, point b) {
    ld dx = a.x - b.x;
    ld dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

vp cyc_intersec(point a, point b) {
    ld d = dis(a, b);
    if (d > a.c + b.c + EPS || d < abs(a.c - b.c) - EPS) {
        return {};
    }

    ld p = acos(max(-1.0l, min(1.0l, (a.c * a.c + d * d - b.c * b.c) / (2 * a.c * d))));
    ld t = atan2(b.y - a.y, b.x - a.x);

    point p1, p2;
    p1.x = a.x + a.c * cos(t + p);
    p1.y = a.y + a.c * sin(t + p);
    p2.x = a.x + a.c * cos(t - p);
    p2.y = a.y + a.c * sin(t - p);

    return {p1, p2};
}

int calc(point x, const vp &cyc) {
    int r = 0;
    for (point y : cyc) {
        if (dis(x, y) < y.c + EPS) {
            r++;
        }
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vp p(n);
    for (int i = 0; i < n; i++) {
        cin >> p.at(i).x >> p.at(i).y >> p.at(i).c;
    }

    if (k == 1) {
        cout << 0 << endl;
        return 0;
    }

    ld l = 0, r = 2e5;
    for (int q = 0; q < M; q++) {
        ld mid = (l + r) / 2;

        vp cyc(n);
        for (int i = 0; i < n; i++) {
            cyc.at(i).x = p.at(i).x;
            cyc.at(i).y = p.at(i).y;
            cyc.at(i).c = mid / p.at(i).c;
        }

        bool f = false;

        for (point x : p) {
            if (calc(x, cyc) >= k) {
                f = true;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                vp t = cyc_intersec(cyc.at(i), cyc.at(j));
                for (point x : t) {
                    if (calc(x, cyc) >= k) {
                        f = true;
                    }
                }
            }
        }

        if (f) {
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << fixed << setprecision(7) << r << endl;

    return 0;
}

```