#include<bits/stdc++.h>
#define mems(a,x) memset(a,x,sizeof(a))
#define first fi
#define second se
using namespace std;
typedef long long ll;
const int mod=1e9+7,MS=105,N=66;
const double eps=1e-8;
ll inv(ll x){return x==1?x:(mod-mod/x)*inv(mod%x)%mod;}
ll inv(ll x,ll mod){return x==1?x:(mod-mod/x)*inv(mod%x,mod)%mod;}
ll qpow(ll a,ll n){ll ans=1;while(n){if(n&1) ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;}
ll mul(ll a,ll b){ll ans=0;while(b){if(b&1) ans=(ans+a)%mod;a=(a+a)%mod;b>>=1;};return ans;}
ll qpow(ll a,ll n,ll mod){ll ans=1;while(n){if(n&1) ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;}
ll mul(ll a,ll b,ll mod){ll ans=0;while(b){if(b&1) ans=(ans+a)%mod;a=(a+a)%mod;b>>=1;};return ans;}
struct vec
{
    double x,y;
    vec(double x=0,double y=0):x(x),y(y){}
    vec operator+(const vec&o)const{ return vec(x+o.x,y+o.y);}
    vec operator-(const vec&o)const{ return vec(x-o.x,y-o.y);}
    double operator*(const vec&o)const{ return x*o.x+y*o.y;}
    double operator^(const vec&o)const{ return x*o.y-y*o.x;}
    vec operator/(const double&o)const{ return vec(x/o,y/o);}
    vec operator*(const double&o)const{ return vec(x*o,y*o);}
    void sc(){scanf("%lf%lf",&x,&y);}
    double len(){return sqrt(x*x+y*y);}
};
struct Mat
{
    ll a[MS][MS];
    int n,m;
    Mat(int n=0,int m=0):n(n),m(m) { mems(a,0);}
    Mat operator*(const Mat&B)const
    {
        Mat C(n,B.m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=B.m;j++)
                for(int k=1;k<=m;k++)
                C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%mod;
        return C;
    }
};
int n,k;
vec a[N];
double c[N];
vec s1,s2;
vec polar(double a,double r){return vec(cos(r)*a,sin(r)*a);}
bool intersect(vec c1,vec c2,double r1,double r2)
{
    double d=(c1-c2).len();
    if(d-eps>r1+r2||d<=r1||d<=r2) return false;
    double a=acos((r1*r1+d*d-r2*r2)/(2*r1*d));
    double t=atan2(c2.y-c1.y,c2.x-c1.x);
    s1=c1+polar(r1,t-a);
    s2=c1+polar(r1,t+a);
    return true;
}
bool judge(double T)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(!intersect(a[i],a[j],T/c[i],T/c[j])) continue;
            int x=0,y=0;
            for(int k=1;k<=n;k++)
            {
                if(c[k]*(s1-a[k]).len()<=T+eps) x++;
                if(c[k]*(s2-a[k]).len()<=T+eps) y++;
            }
            if(x>=k||y>=k) return true;
        }
        int x=0;
        for(int j=1;j<=n;j++)
            if(c[j]*(a[i]-a[j]).len()<=T+eps) x++;
        if(x>=k) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        a[i].sc(),scanf("%lf",&c[i]);
    double l=0,r=200000;
    for(int i=1;i<=50;i++)
    {
        double m=(l+r)/2;
        if(judge(m)) r=m;
        else l=m;
    }
    printf("%.10f\n",(l+r)/2);
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
#define mems(a,x) memset(a,x,sizeof(a))
#define first fi
#define second se
using namespace std;
typedef long long ll;
const int mod=1e9+7,MS=105,N=66;
const double eps=1e-8;
ll inv(ll x){return x==1?x:(mod-mod/x)*inv(mod%x)%mod;}
ll inv(ll x,ll mod){return x==1?x:(mod-mod/x)*inv(mod%x,mod)%mod;}
ll qpow(ll a,ll n){ll ans=1;while(n){if(n&1) ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;}
ll mul(ll a,ll b){ll ans=0;while(b){if(b&1) ans=(ans+a)%mod;a=(a+a)%mod;b>>=1;};return ans;}
ll qpow(ll a,ll n,ll mod){ll ans=1;while(n){if(n&1) ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;}
ll mul(ll a,ll b,ll mod){ll ans=0;while(b){if(b&1) ans=(ans+a)%mod;a=(a+a)%mod;b>>=1;};return ans;}
struct vec
{
    double x,y;
    vec(double x=0,double y=0):x(x),y(y){}
    vec operator+(const vec&o)const{ return vec(x+o.x,y+o.y);}
    vec operator-(const vec&o)const{ return vec(x-o.x,y-o.y);}
    double operator*(const vec&o)const{ return x*o.x+y*o.y;}
    double operator^(const vec&o)const{ return x*o.y-y*o.x;}
    vec operator/(const double&o)const{ return vec(x/o,y/o);}
    vec operator*(const double&o)const{ return vec(x*o,y*o);}
    void sc(){scanf("%lf%lf",&x,&y);}
    double len(){return sqrt(x*x+y*y);}
};
struct Mat
{
    ll a[MS][MS];
    int n,m;
    Mat(int n=0,int m=0):n(n),m(m) { mems(a,0);}
    Mat operator*(const Mat&B)const
    {
        Mat C(n,B.m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=B.m;j++)
                for(int k=1;k<=m;k++)
                C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%mod;
        return C;
    }
};
int n,k;
vec a[N];
double c[N];
vec s1,s2;
vec polar(double a,double r){return vec(cos(r)*a,sin(r)*a);}
bool intersect(vec c1,vec c2,double r1,double r2)
{
    double d=(c1-c2).len();
    if(d-eps>r1+r2||d<=r1||d<=r2) return false;
    double a=acos((r1*r1+d*d-r2*r2)/(2*r1*d));
    double t=atan2(c2.y-c1.y,c2.x-c1.x);
    s1=c1+polar(r1,t-a);
    s2=c1+polar(r1,t+a);
    return true;
}
bool judge(double T)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(!intersect(a[i],a[j],T/c[i],T/c[j])) continue;
            int x=0,y=0;
            for(int k=1;k<=n;k++)
            {
                if(c[k]*(s1-a[k]).len()<=T+eps) x++;
                if(c[k]*(s2-a[k]).len()<=T+eps) y++;
            }
            if(x>=k||y>=k) return true;
        }
        int x=0;
        for(int j=1;j<=n;j++)
            if(c[j]*(a[i]-a[j]).len()<=T+eps) x++;
        if(x>=k) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        a[i].sc(),scanf("%lf",&c[i]);
    double l=0,r=200000;
    for(int i=1;i<=50;i++)
    {
        double m=(l+r)/2;
        if(judge(m)) r=m;
        else l=m;
    }
    printf("%.10f\n",(l+r)/2);
}

```