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;

typedef long long ll;
const int maxn=67;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
//#define int ll

#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

int n,k;
int x[maxn],y[maxn],c[maxn];
long double r[maxn];

const long double eps=(1e-10);

int check2(long double X,long double Y)
{
    int cnt=0;
    for (int i=1;i<=n;i++)
        cnt+=(hypot(X-x[i],Y-y[i])<=r[i]+eps);
    return cnt>=k;
}

void get_intersection(int X,int Y,vector<pair<long double,long double> > &v)
{
    long double dist=hypot(x[X]-x[Y],y[X]-y[Y]);
    if (dist>r[X]+r[Y]||dist<abs(r[X]-r[Y])) return;

    long double costheta=(r[X]*r[X]+dist*dist-r[Y]*r[Y])/(2*r[X]*dist);
    long double sintheta=sqrt(1.0-costheta*costheta);

    long double xx=(x[Y]-x[X])*(r[X]/dist),yy=(y[Y]-y[X])*(r[X]/dist);

    v.pb(mkp(x[X]+xx*costheta-yy*sintheta,y[X]+xx*sintheta+yy*costheta));
    v.pb(mkp(x[X]+xx*costheta+yy*sintheta,y[X]+xx*sintheta-yy*costheta));
}

bool check(long double X)
{
    for (int i=1;i<=n;i++) r[i]=X/c[i];

    vector<pair<long double,long double> > v;

    int ok=0;
    for (int i=1;i<=n;i++) ok=max(ok,check2(x[i],y[i]));
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
    {
        v.clear();
        get_intersection(i,j,v);
        for (auto l:v) ok=max(ok,check2(l.F,l.S));
    }
    return ok;
}

int32_t main()
{
    IOS
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>x[i]>>y[i]>>c[i];

    long double L=0.0,R=500000.0;
    for (int _=1;_<=80;_++)
    {
        long double M=(L+R)/2;
        if (check(M)) R=M;
        else L=M;
    }
    cout<<fixed<<setprecision(15)<<R<<endl;
}