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 <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
typedef long long ll;
int N, K;
double x[60], y[60], c[60];

double dist(double s, double t, int i){
    return sqrt((s-x[i])*(s-x[i])+(t-y[i])*(t-y[i]));
}

double dist(int i, int j){
    return sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> x[i] >> y[i] >> c[i];
    double l = 0.0, r = 200000;
    int ct = 0;
    if(K == 1){
        cout << 0 << endl;
        return 0;
    }
    while(ct < 100){
        ct++;
        double p = (l+r)/2;
        int mx = 0;
        for(int i = 0; i < N; i++){
            for(int j = i+1; j < N; j++){
                double r1 = p/c[j];
                double r2 = p/c[i];
                if(dist(i, j) > r1+r2) continue;
                if(dist(i, j)+min(r1, r2) < max(r1, r2)) continue;
                double x1 = x[i]-x[j], y1 = y[i]-y[j];
                double a = (x1*x1+y1*y1+r1*r1-r2*r2)/2;
                double ds = y1*sqrt((x1*x1+y1*y1)*r1*r1-a*a)/(x1*x1+y1*y1);
                double dt = x1*sqrt((x1*x1+y1*y1)*r1*r1-a*a)/(x1*x1+y1*y1);
                double os = x[j]+a*x1/(x1*x1+y1*y1);
                double ot = y[j]+a*y1/(x1*x1+y1*y1);
                double s = os+ds;
                double t = ot-dt;
                int cnt = 0;
                for(int k = 0; k < N; k++){
                    if(dist(s, t, k) < p/c[k]) cnt++;
                }
                mx = max(mx, cnt);
                s = os-ds;
                t = ot+dt;
                cnt = 0;
                for(int k = 0; k < N; k++){
                    if(dist(s, t, k) < p/c[k]+1e-8) cnt++;
                }
                mx = max(mx, cnt);
            }
        }
        // cout << mx << "->";
        for(int i = 0; i < N; i++){
            int cnt = 0;
            for(int j = 0; j < N; j++){
                if(dist(i, j)+p/c[i] < p/c[j]+1e-8) cnt++;
            }
            mx = max(cnt, mx);
        }
        // cout << mx << endl;
        if(mx >= K) r = p;
        else l = p;
    }
    cout << l << endl;
}