#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
using Real = long double;
using Point = complex< Real >;
const Real EPS = 1e-12, PI = acos(-1.0L);

inline bool eq(Real a,Real b){ return fabs(b-a)<EPS;}
istream &operator>>(istream &is, Point &p) {
  Real a, b;
  is >> a >> b;
  p = Point(a, b);
  return is;
}
struct Circle{
    Point p;  //centre co-ordinate 
    Real r;     // radius of circle

    Circle()=default;
    Circle(Point p,Real r): p(p),r(r){}
};
using Points=vector<Point>;
using Circles=vector<Circle>;

int checker(Circle c1,Circle c2){
    if(c1.r<c2.r) swap(c1,c2);  //c1 is bigger circle finally
    Real d=abs(c1.p-c2.p);
    if(c1.r+c2.r<d) return 4;   // circles dont touch
    if(eq(c1.r+c2.r,d)) return 3;    // circles touch
    if(c1.r-c2.r<d) return 2;         // intersect at two points
    if(eq(c1.r-c2.r,d)) return 1;       //smaller is inside and touching bigger
    return 0;
}
bool intersect(Circle c1,Circle c2){
    int temp=checker(c1,c2);
    return 1<=temp&&temp<=3;
}
pair<Point,Point> crosspoint(const Circle &c1,const Circle &c2){
    Real d=abs(c1.p-c2.p);
    Real a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
    Real t=atan2(c2.p.imag()-c1.p.imag(),c2.p.real()-c1.p.real());
    Point p1=c1.p+Point(cos(t+a)*c1.r,sin(t+a)*c1.r);
    Point p2=c1.p+Point(cos(t-a)*c1.r,sin(t-a)*c1.r);
    return {p1,p2};
}
int N,K;
Points P;
vector<int> c;
vector<long double> r;
Circles C;
void input(){
    cin>>N>>K;
    P.resize(N);
    c.resize(N);
    C.resize(N);
    r.resize(N);
    for(int i = 0; i < N; i++) {
        cin>>P[i]>>c[i];
    }
}

void solve(){
    long double ok=1e6;
    long double ng=0.0;
    F0R(timer,41){
        bool clear=false;
        long double mid=(ok+ng)/2.0;
        F0R(i,N){
            r[i]=mid/c[i];
            C[i]=Circle(P[i],r[i]);
        }
        Points Check;
        F0R(i,N){
            Check.push_back(P[i]);
            FOR(j,1,N){
                if(intersect(C[i],C[j])){
                    auto tmp=crosspoint(C[i],C[j]);
                    Check.push_back(tmp.first);
                    Check.push_back(tmp.second);
                }
            }
        }
        for(auto p:Check){
            int cnt=0;
            F0R(i,N){
                if(abs(P[i]-p)<=r[i]+EPS){
                    cnt++;
                }
            }
            if(cnt>=K){
                clear=true;
            }
        }
        if(clear){
            ok=mid;
        }else{
            ng=mid;
        }
    }
    cout.precision(20);
    cout<<ok<<endl;
}

int main(){
    input();
    solve();
    return 0;
}

### Prompt

Create a solution in cpp for the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
using Real = long double;
using Point = complex< Real >;
const Real EPS = 1e-12, PI = acos(-1.0L);

inline bool eq(Real a,Real b){ return fabs(b-a)<EPS;}
istream &operator>>(istream &is, Point &p) {
  Real a, b;
  is >> a >> b;
  p = Point(a, b);
  return is;
}
struct Circle{
    Point p;  //centre co-ordinate 
    Real r;     // radius of circle

    Circle()=default;
    Circle(Point p,Real r): p(p),r(r){}
};
using Points=vector<Point>;
using Circles=vector<Circle>;

int checker(Circle c1,Circle c2){
    if(c1.r<c2.r) swap(c1,c2);  //c1 is bigger circle finally
    Real d=abs(c1.p-c2.p);
    if(c1.r+c2.r<d) return 4;   // circles dont touch
    if(eq(c1.r+c2.r,d)) return 3;    // circles touch
    if(c1.r-c2.r<d) return 2;         // intersect at two points
    if(eq(c1.r-c2.r,d)) return 1;       //smaller is inside and touching bigger
    return 0;
}
bool intersect(Circle c1,Circle c2){
    int temp=checker(c1,c2);
    return 1<=temp&&temp<=3;
}
pair<Point,Point> crosspoint(const Circle &c1,const Circle &c2){
    Real d=abs(c1.p-c2.p);
    Real a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
    Real t=atan2(c2.p.imag()-c1.p.imag(),c2.p.real()-c1.p.real());
    Point p1=c1.p+Point(cos(t+a)*c1.r,sin(t+a)*c1.r);
    Point p2=c1.p+Point(cos(t-a)*c1.r,sin(t-a)*c1.r);
    return {p1,p2};
}
int N,K;
Points P;
vector<int> c;
vector<long double> r;
Circles C;
void input(){
    cin>>N>>K;
    P.resize(N);
    c.resize(N);
    C.resize(N);
    r.resize(N);
    for(int i = 0; i < N; i++) {
        cin>>P[i]>>c[i];
    }
}

void solve(){
    long double ok=1e6;
    long double ng=0.0;
    F0R(timer,41){
        bool clear=false;
        long double mid=(ok+ng)/2.0;
        F0R(i,N){
            r[i]=mid/c[i];
            C[i]=Circle(P[i],r[i]);
        }
        Points Check;
        F0R(i,N){
            Check.push_back(P[i]);
            FOR(j,1,N){
                if(intersect(C[i],C[j])){
                    auto tmp=crosspoint(C[i],C[j]);
                    Check.push_back(tmp.first);
                    Check.push_back(tmp.second);
                }
            }
        }
        for(auto p:Check){
            int cnt=0;
            F0R(i,N){
                if(abs(P[i]-p)<=r[i]+EPS){
                    cnt++;
                }
            }
            if(cnt>=K){
                clear=true;
            }
        }
        if(clear){
            ok=mid;
        }else{
            ng=mid;
        }
    }
    cout.precision(20);
    cout<<ok<<endl;
}

int main(){
    input();
    solve();
    return 0;
}

```