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


using namespace std;
typedef long double ld;
typedef long long ll;
const int MAX = 60;
typedef complex<long double> Point;


namespace std {
    bool operator<(const Point &lhs, const Point &rhs) {
        return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real();
    }
}

struct Circle {
    Point c;
    ld r;

    vector<Point> cross(const Circle &other) {
        vector<Point> ret;
        ld dist = abs(c - other.c);
        ld rc = (dist * dist + r * r - other.r * other.r) / (2 * dist);
        ld dfr = r * r - rc * rc;
        if (abs(dfr) < 1e-6) dfr = 0.0;
        if (dfr < 0.0) {
            return ret;
        }
        ld rs = sqrt(dfr);
        Point diff = (other.c - c) / dist;
        ret.push_back(c + diff * Point{rc, rs});
        if (dfr != 0.0) {
            ret.push_back(c + diff * Point{rc, -rs});
        }
        return ret;
    }
};

const ld eps = 1e-9;
int n, k;
Circle m[MAX + 1];
int c[MAX + 1];


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    cin >> n >> k;

    vector<Point> centers;
    for (int i = 0; i < n; ++i) {
        ld xc, yc;
        cin >> xc >> yc >> c[i];
        m[i] = {Point{xc, yc}};
        centers.push_back(m[i].c);
    }

    ld hi = 1e6;
    ld lo = 0;
    for (int ii = 0; ii < 100; ++ii) {
        ld t = lo + (hi - lo) / 2;
        vector<Point> candidate(centers);

        for (int i = 0; i < n; ++i) {
            m[i].r = (ld) t / (ld) c[i];
            for (int j = i + 1; j < n; ++j) {
                m[j].r = (ld) t / (ld) c[j];
                auto ret = m[i].cross(m[j]);
                for (auto pt : ret) {
                    candidate.push_back(pt);
                }
            }
        }

        int mc = 0;
        for (auto pt : candidate) {
            int count = 0;
            for (int i = 0; i < n; ++i) {
                ld diff = abs(m[i].c - pt);
                if (diff < m[i].r + eps) {
                    ++count;
                }
            }
            mc = count;
            if (count >= k) {
                break;
            }
        }

        if (mc < k) {
            lo = t + eps;
        } else {
            hi = t;
        }
    }

    cout << lo;

    return 0;
}