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;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ld double
#define pb push_back
const int MAXN = 65;
const ld EPS = 1e-6, DOIS = 2;
int cnt = 0;
ld x[MAXN], y[MAXN], c[MAXN];
ld modulo(ld g){return (g<0) ? -g : g;}
int main(){
    fastio;
    int n,k; cin>>n>>k;
    for(int i=1; i<=n; i++){
        cin>>x[i]>>y[i]>>c[i];
    }
    if(k==1){cout<<"0"<<endl; return 0;}
    ld l = 0;
    ld r = 1e6;
    while(r - l > EPS){
        ld t = (l + r)/DOIS;
        bool achei = false;

        for(int i=1; i<=n; i++){//testando centros
            int discos = 0;
            for(int j=1; j<=n; j++){
                ld dist = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
                if(dist <= t/c[j] + EPS)discos++;
            }
            if(discos >= k)achei = true;
        }

        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){

                ld raio_i = t/c[i];
                ld raio_j = t/c[j];

                ld x_medio = (x[i] + x[j])/DOIS;
                ld y_medio = (y[i] + y[j])/DOIS;

                ld dist_centros = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
                if(modulo(dist_centros) > raio_i + raio_j)continue;//nao intersectam

                ld d1 = (dist_centros*dist_centros + raio_i*raio_i - raio_j*raio_j)/(DOIS*dist_centros);

                ld x_P = x[i] + (x[j]-x[i])*d1/dist_centros;
                ld y_P = y[i] + (y[j]-y[i])*d1/dist_centros;

                ld x_perp = y[j] - y[i];
                ld y_perp = x[i] - x[j];

                ld norma_perpSQ = x_perp*x_perp + y_perp*y_perp;
                ld normaSQ = (x_P-x[i])*(x_P-x[i]) + (y_P-y[i])*(y_P-y[i]);
                ld k2 = sqrt((raio_i*raio_i - normaSQ)/norma_perpSQ);

                // INTERSECCOES
                int discos1 = 0;
                ld x1 = x_P + k2*x_perp;
                ld y1 = y_P + k2*y_perp;
                for(int g=1; g<=n; g++){
                    ld dist = sqrt((x1-x[g])*(x1-x[g]) + (y1-y[g])*(y1-y[g]));
                    if(dist <= t/c[g] + EPS)discos1++;
                }
                if(discos1 >= k)achei = true;
                
                int discos2 = 0;
                ld x2 = x_P - k2*x_perp;
                ld y2 = y_P - k2*y_perp;
                for(int g=1; g<=n; g++){
                    ld dist = sqrt((x2-x[g])*(x2-x[g]) + (y2-y[g])*(y2-y[g]));
                    if(dist <= t/c[g] + EPS)discos2++;
                }
                if(discos2 >= k)achei = true;
            }
        }
        if(achei)r = t;
        else l = t;
    }
    cout<<setprecision(7)<<l<<endl;
}