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>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>

int n,k;
double x[100],y[100],c[100];
double EPS=1e-7;

struct Point{
    double x,y;
    Point(double xx,double yy){
        x=xx;
        y=yy;
    }
};

struct Circle{
    double x,y,r;
    Circle(double xx,double yy,double rr){
        x=xx;
        y=yy;
        r=rr;
    }
};
bool is_in_cercle(Point p,Circle c){
    double x1=p.x,y1=p.y;
    double x2=c.x,y2=c.y,r=c.r;
    //double r=sqrt(x1*x1+y1*y1);
    double dx=x1-x2,dy=y1-y2;
    double dist=sqrt(dx*dx+dy*dy);
    return dist<r+EPS;
}
bool is_cross(Circle a,Circle b){
    double dist=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    if(a.r+b.r < dist)
        return 0;
    if(a.r+dist<b.r || b.r+dist<a.r)
        return 0;
    
    return 1;
}
bool ok(double ans){
    vector<Circle>ci;
    vector<Point>koho;
    ci.clear();
    koho.clear();

    for(int i=0;i<n;i++){
        ci.pb(Circle(x[i],y[i],ans/c[i]));
        koho.pb(Point(x[i],y[i]));
    }

   for(int i=0;i<n;i++){
       for(int j=i+1;j<n;j++){
            double x1,y1,x2,y2,r1,r2,a;
            x1=ci[i].x;
            y1=ci[i].y;
            r1=ci[i].r;

            x2=ci[j].x;
            y2=ci[j].y;
            r2=ci[j].r;
            x1-=x2;y1-=y2;
            x2=y2=0.0;

            a=(x1*x1+y1*y1+r2*r2-r1*r1)/2;

            double ax1,ax2,ay1,ay2;
            //if((x1*x1+y1*y1)*r1*r1-a*a+EPS > 0.0){
            if(is_cross(ci[i],ci[j])){
            ax1=(a*x1+y1*sqrt((x1*x1+y1*y1)*r2*r2-a*a))/(x1*x1+y1*y1); 
            ay1=(a*y1-x1*sqrt((x1*x1+y1*y1)*r2*r2-a*a))/(x1*x1+y1*y1); 
            ax2=(a*x1-y1*sqrt((x1*x1+y1*y1)*r2*r2-a*a))/(x1*x1+y1*y1); 
            ay2=(a*y1+x1*sqrt((x1*x1+y1*y1)*r2*r2-a*a))/(x1*x1+y1*y1); 
            koho.pb(Point(ax1+ci[j].x,ay1+ci[j].y));
            koho.pb(Point(ax2+ci[j].x,ay2+ci[j].y));
            //assert((x1*x1+y1*y1)*r1*r1-a*a<0.0);
            //cout<<a<<" "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<ax1<<" "<<ay1<<" "<<ax2<<" "<<ay2<<endl;
            }
       }
   } 
    rep(i,koho.size()){
        int cnt=0;
        rep(j,n){
            if(is_in_cercle(koho[i],ci[j]))
                cnt++;
        }
        //cout<<ans<<" "<<cnt<<" "<<koho[i].x<<" "<<koho[i].y<<endl;
        if(cnt>=k){
         //   cout<<endl;
            return true;
        }
    }
    //cout<<endl;
    return false;
}

int main() {
    cin>>n>>k;
    rep(i,n)cin>>x[i]>>y[i]>>c[i];

    double l=0.0,r=100000000.0;

    rep(ii,200){
        double mid=(r+l)/2;
        if(ok(mid))
            r=mid;
        else
            l=mid;
    }
 
    printf("%.10lf\n",l);

    return 0;
}