#include <bits/stdc++.h>

using namespace std;

const long double EPS = 1e-8;

void interC(vector<pair<long double, long double>> &res, long double x1, long double y1, long double r1, long double x2, long double y2, long double r2) {
    auto dx = x2 - x1;
    auto dy = y2 - y1;
    auto d = sqrt(dx*dx + dy*dy);
    if (d <= 0.0) {
        return;
    }
    auto l = (r1*r1 - r2*r2) / (2*d) + d/2;
    auto hsq = r1*r1 - l*l;
    if (hsq < 0.0) {
        return;
    }
    auto h = sqrt(hsq);
    auto xl = dx*l/d;
    auto xr = dy*h/d;
    auto yl = dy*l/d;
    auto yr = dx*h/d;
    res.push_back({xl+xr+x1, yl-yr+y1});
    res.push_back({xl-xr+x1, yl+yr+y1});
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> a(n);
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second >> c[i];
    }
    long double l = 0.0;
    long double r = 1e9;
    while (r-l > EPS) {
        long double mid = (l+r)/2;
        vector<pair<long double, long double>> pts;
        for (auto pr: a) {
            pts.push_back({1.0*pr.first, 1.0*pr.second});
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                interC(pts, a[i].first, a[i].second, mid/c[i], a[j].first, a[j].second, mid/c[j]);
            }
        }
        bool ok = false;
        for (auto pr: pts) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                long double dx = pr.first - a[i].first;
                long double dy = pr.second - a[i].second;
                long double tm = c[i]*sqrt(dx*dx + dy*dy);
                if (tm <= mid+EPS) {
                    cnt++;
                }
            }
            if (cnt >= k) {
                ok = true;
            }
        }
        if (ok) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout.precision(10);
    cout << fixed << l << endl;
}



### Prompt

Generate 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 <bits/stdc++.h>

using namespace std;

const long double EPS = 1e-8;

void interC(vector<pair<long double, long double>> &res, long double x1, long double y1, long double r1, long double x2, long double y2, long double r2) {
    auto dx = x2 - x1;
    auto dy = y2 - y1;
    auto d = sqrt(dx*dx + dy*dy);
    if (d <= 0.0) {
        return;
    }
    auto l = (r1*r1 - r2*r2) / (2*d) + d/2;
    auto hsq = r1*r1 - l*l;
    if (hsq < 0.0) {
        return;
    }
    auto h = sqrt(hsq);
    auto xl = dx*l/d;
    auto xr = dy*h/d;
    auto yl = dy*l/d;
    auto yr = dx*h/d;
    res.push_back({xl+xr+x1, yl-yr+y1});
    res.push_back({xl-xr+x1, yl+yr+y1});
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> a(n);
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second >> c[i];
    }
    long double l = 0.0;
    long double r = 1e9;
    while (r-l > EPS) {
        long double mid = (l+r)/2;
        vector<pair<long double, long double>> pts;
        for (auto pr: a) {
            pts.push_back({1.0*pr.first, 1.0*pr.second});
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                interC(pts, a[i].first, a[i].second, mid/c[i], a[j].first, a[j].second, mid/c[j]);
            }
        }
        bool ok = false;
        for (auto pr: pts) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                long double dx = pr.first - a[i].first;
                long double dy = pr.second - a[i].second;
                long double tm = c[i]*sqrt(dx*dx + dy*dy);
                if (tm <= mid+EPS) {
                    cnt++;
                }
            }
            if (cnt >= k) {
                ok = true;
            }
        }
        if (ok) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout.precision(10);
    cout << fixed << l << endl;
}



```