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 ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll N, K;

ll i, j, k;
ll X[66], Y[66],C[66];

double p2(double a){
    return a * a;
}

bool ck(double x,double y,double a){
    //cout << x << "," << y << ",";
    ll i,k=0;
    fornum(i,0,N){
        double rr = sqrt(p2(X[i] - x) + p2(Y[i] - y)) * C[i];
        if(rr<=a+1e-8){
            ++k;
        }
    }
    //cout << k << endl;
    return k >= K;
}

bool bs(double a){
    ll i, j;
    fornum(i,0,N){
        if(ck(X[i],Y[i],a))
            return true;
    }
    fornum(i,0,N){
        fornum(j,i+1,N){
            double at = a / C[i];
            double bt = a / C[j];
            double d = sqrt(p2((double)X[i] - X[j]) + p2((double)Y[i] - Y[j]));
            //cout << i << "<<" << j << endl;
            //cout << at << "," << bt << "," << d << endl;
            if(d>at+bt)
                continue;
            //cout << i << "-" << j << endl;
            double ac = (p2(d) + p2(at) - p2(bt)) / (2 * at * d);
            if(p2(ac)>1)
                continue;
            double as = sqrt(1 - p2(ac));
            double gx = (X[j] - X[i]) / d, gy = (Y[j] - Y[i]) / d;
            double ogx = -gy, ogy = gx;
            double x, y;
            //cout << ac << as << endl;
            x = X[i] + at * ac * gx + at * as * ogx;
            y = Y[i] + at * ac * gy + at * as * ogy;
            if(ck(x,y,a)){
                //cout << "aa" << ac << "," << as << endl;
                //cout << x << "," << y << "," << a << endl;
                return true;
            }
            x = X[i] + at * ac * gx - at * as * ogx;
            y = Y[i] + at * ac * gy - at * as * ogy;
            if(ck(x,y,a)){
                //cout << "bb" << at << "," << bt << endl;
                //cout << x << "," << y << "," << a << endl;
                return true;
            }
        }
    }
    return false;
}

int main(){
    scanf("%lld%lld", &N, &K);
    fornum(i,0,N){
        scanf("%lld%lld%lld", &X[i], &Y[i], &C[i]);
    }
    double l = 0, r = 1e8;
    //bs(2.4+1e-8);
    //return 0;
    while(l+1e-8<r){
        double c = (l + r) / 2;
        if(bs(c)){
            r = c;
        }else{
            l = c + 1e-8;
        }
    }
    printf("%.12lf", l);
    return 0;
}