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 complex<double> Point;
#define LE(n,m) ((n)<(m)+EPS)
#define GE(n,m) ((n)+EPS>(m))
#define EQ(n,m) (abs((n)-(m))<EPS)
const double EPS=1e-8;
struct Circle{Point center; double r;};

vector<Point> crosspointCC(const Circle &c1,const Circle &c2){
    vector<Point> ps;
    Point ls=c2.center-c1.center;
    double dist=abs(ls);
    double crL=(norm(ls)+c1.r*c1.r-c2.r*c2.r)/(2.0*dist);
    if (EQ(dist,0)||c1.r<abs(crL)) return ps;
    Point dir=ls*Point(0.0,sqrt(c1.r*c1.r-crL*crL)/dist);
    Point mc=c1.center+crL/dist*ls;
    ps.emplace_back(mc+dir);
    if (!EQ(norm(dir),0.0)) ps.emplace_back(mc-dir);
    return ps;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    int N,K; cin >> N >> K;
    vector<Point> ps;
    vector<double> cs;
    for (int i=0;i<N;++i){
        double x,y,c; cin >> x >> y >> c;
        ps.emplace_back(x,y);
        cs.emplace_back(c);
    }
    double lb=0,ub=1e9;
    while(ub-lb>1e-7){
        double mid=(ub+lb)/2.0;
        vector<Point> cand;
        vector<Circle> checks;
        for (int i=0;i<N;++i){
            Circle C={ps[i],mid/cs[i]};
            checks.emplace_back(C);
        }
        for (int i=0;i<N;++i){
            cand.emplace_back(ps[i]);
            for (int j=i+1;j<N;++j){
                vector<Point> cps=crosspointCC(checks[i],checks[j]);
                for (Point p:cps) cand.emplace_back(p);
            }
        }
        int ok=0;
        for (Point p:cand){
            int cnt=0;
            for (int i=0;i<N;++i)
                if (LE(abs(p-checks[i].center),checks[i].r))
                    ++cnt;
            if (cnt>=K) ok=1;
        }
        (ok?ub:lb)=mid;
    }
    cout << ub << '\n';
}