#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int N, K;
double x[60], y[60], c[60];

// 円 i, j の交点を求める
pair<double, double> calc_point(int i, int j, double t, int p){
    // https://shogo82148.github.io/homepage/memo/geometry/circle-cross.html
    double x_1 = x[j]-x[i];
    double y_1 = y[j]-y[i];
    double r_1 = t / c[i];
    double r_2 = t / c[j];
    double a = x_1*x_1 + y_1*y_1 + r_1*r_1 - r_2*r_2;
    a /= 2.0;
    if(p == 1){
        double X = a*x_1 + y_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        X /= x_1*x_1 + y_1*y_1;
        X += x[i];
        double Y = a*y_1 - x_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        Y /= x_1*x_1 + y_1*y_1;
        Y += y[i];
        return mp(X, Y);
    }
    else{
        double X = a*x_1 - y_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        X /= x_1*x_1 + y_1*y_1;
        X += x[i];
        double Y = a*y_1 + x_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        Y /= x_1*x_1 + y_1*y_1;
        Y += y[i];
        return mp(X, Y);
    }
}

double dist(double x_1, double y_1, double x_2, double y_2){
    return sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2));
}

// t 秒以内に K 枚の肉を焼くことができる熱源の位置は存在するか
bool isOK(double t){
    // 各肉 i について，その位置から半径 t/c_i 以内の位置に熱源を置けば t 秒以内に焼ける
    // よって「中心 (x_i, y_i) 半径 t/c_i の円が K 個以上重なる点があるか」が必要十分条件
    // 2 円の交点だけ調べれば十分
    rep(i, N){
        rep(j, N){
            if(i >= j) continue;
            rep(k, 2){
                pair<double, double> p = calc_point(i, j, t, k);
                int cnt = 0;
                rep(l, N){
                    if(dist(p.first, p.second, x[l], y[l]) <= t/c[l] + 1e-8) cnt++;
                }
                if(cnt >= K) return true;
            }
            rep(k, 2){
                pair<double, double> p = mp(x[(k==0 ? i : j)], y[(k==0 ? i : j)]);
                int cnt = 0;
                rep(l, N){
                    if(dist(p.first, p.second, x[l], y[l]) <= t/c[l] + 1e-8) cnt++;
                }
                if(cnt >= K) return true;
            }
        }
    }
    return false;
}

signed main(){
    cin >> N >> K;
    rep(i, N) cin >> x[i] >> y[i] >> c[i];

    if(K == 1){
        cout << 0 << endl;
        return 0;
    }
    
    double ok = 300000;
    double ng = -1;
    while(ok - ng > 1e-8){
        double m = (ok+ng)/2;
        if(isOK(m)) ok = m;
        else ng = m;
    }
    cout << fixed << setprecision(16) << ok << endl;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int N, K;
double x[60], y[60], c[60];

// 円 i, j の交点を求める
pair<double, double> calc_point(int i, int j, double t, int p){
    // https://shogo82148.github.io/homepage/memo/geometry/circle-cross.html
    double x_1 = x[j]-x[i];
    double y_1 = y[j]-y[i];
    double r_1 = t / c[i];
    double r_2 = t / c[j];
    double a = x_1*x_1 + y_1*y_1 + r_1*r_1 - r_2*r_2;
    a /= 2.0;
    if(p == 1){
        double X = a*x_1 + y_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        X /= x_1*x_1 + y_1*y_1;
        X += x[i];
        double Y = a*y_1 - x_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        Y /= x_1*x_1 + y_1*y_1;
        Y += y[i];
        return mp(X, Y);
    }
    else{
        double X = a*x_1 - y_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        X /= x_1*x_1 + y_1*y_1;
        X += x[i];
        double Y = a*y_1 + x_1*sqrt((x_1*x_1+y_1*y_1)*r_1*r_1 - a*a);
        Y /= x_1*x_1 + y_1*y_1;
        Y += y[i];
        return mp(X, Y);
    }
}

double dist(double x_1, double y_1, double x_2, double y_2){
    return sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2));
}

// t 秒以内に K 枚の肉を焼くことができる熱源の位置は存在するか
bool isOK(double t){
    // 各肉 i について，その位置から半径 t/c_i 以内の位置に熱源を置けば t 秒以内に焼ける
    // よって「中心 (x_i, y_i) 半径 t/c_i の円が K 個以上重なる点があるか」が必要十分条件
    // 2 円の交点だけ調べれば十分
    rep(i, N){
        rep(j, N){
            if(i >= j) continue;
            rep(k, 2){
                pair<double, double> p = calc_point(i, j, t, k);
                int cnt = 0;
                rep(l, N){
                    if(dist(p.first, p.second, x[l], y[l]) <= t/c[l] + 1e-8) cnt++;
                }
                if(cnt >= K) return true;
            }
            rep(k, 2){
                pair<double, double> p = mp(x[(k==0 ? i : j)], y[(k==0 ? i : j)]);
                int cnt = 0;
                rep(l, N){
                    if(dist(p.first, p.second, x[l], y[l]) <= t/c[l] + 1e-8) cnt++;
                }
                if(cnt >= K) return true;
            }
        }
    }
    return false;
}

signed main(){
    cin >> N >> K;
    rep(i, N) cin >> x[i] >> y[i] >> c[i];

    if(K == 1){
        cout << 0 << endl;
        return 0;
    }
    
    double ok = 300000;
    double ng = -1;
    while(ok - ng > 1e-8){
        double m = (ok+ng)/2;
        if(isOK(m)) ok = m;
        else ng = m;
    }
    cout << fixed << setprecision(16) << ok << endl;
}
```