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>
#define maxn 65
#define MOD 998244353
#define INF 10000000000

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define piii pair<ll, pii>
#define ft first
#define sd second

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

ll n, k;
ll x[maxn], y[maxn], c[maxn];
const double er = 0.00000001;

bool check(double t){
    for(ll i = 0; i  < n; i++){
        for(ll j = i; j < n; j++){
            if(i == j){
                ll cnt = 0;
                for(ll l = 0; l < n; l++){
                    double r = t/c[l];
                    double dis = (x[l]-x[i])*(x[l]-x[i]) + (y[l]-y[i])*(y[l]-y[i]);
                    if(dis <= r*r + er) cnt++;
                }
                if(cnt >= k) return true;

            }
            else{
                // calculate intersection
                // https://poporix.hatenablog.com/
                double xd = x[j]-x[i], yd = y[j]-y[i];
                double d = sqrt(xd*xd + yd*yd);
                double r1 = t/c[i], r2 = t/c[j];
                double costheta = (r1*r1 + d*d - r2*r2)/ (2*r1*d);
                double rc = r1 * costheta;
                double rs = sqrt(r1*r1 - rc*rc);

                double x1 = x[i] + (xd/d)*rc - (yd/d)*rs, y1 = y[i] + (yd/d)*rc + (xd/d)*rs;
                double x2 = x[i] + (xd/d)*rc + (yd/d)*rs, y2 = y[i] + (yd/d)*rc - (xd/d)*rs;

                ll cnt1 = 0, cnt2 = 0;
                for(ll l = 0; l < n; l++){
                    double r = t/c[l], dis = (x1-x[l])*(x1-x[l]) + (y1-y[l])*(y1-y[l]);
                    if(dis <= r*r + er) cnt1++;

                    dis = (x2-x[l])*(x2-x[l]) + (y2-y[l])*(y2-y[l]);
                    if(dis <= r*r + er) cnt2++;
                }
                if(cnt1 >= k || cnt2 >= k) return true;

            }
        }
    }

    return false;
}

void solve(){
    cin >> n >> k;
    for(ll i = 0; i < n; i++){
        cin >> x[i] >> y[i] >> c[i];
    }
    cout << setprecision(10);

    double mn = 0.0, mx = 100000000.0;
    while(mx - mn > er){
        double md = mn + (mx - mn)/2; //cout << md << " ";
        if(check(md)){
            mx = md;
        }
        else mn = md;
    }
    cout << mn;
}

int main()
{
    fast();
    int t= 1; //cin >> t;
    while(t--){
        solve();
    }
}