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 <iomanip>
#include <cmath>
using namespace std;
typedef pair<double, double> P;
typedef pair<P, P> PP;

const double INF = 1e100;

pair<pair<double, double>, pair<double, double>> circle_cross_point(
    double x0, double y0, double r0, double x1, double y1, double r1){
    if((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) > (r0 + r1) * (r0 + r1) ||
       (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) < (r0 - r1) * (r0 - r1)){
        return pair<pair<double, double>, pair<double, double>>(
            pair<double, double>(INF, INF), 
            pair<double, double>(INF, INF)
        );
    }
    double a = ((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) + r0 * r0 - r1 * r1) / 2;
    double z = ((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
    return pair<pair<double, double>, pair<double, double>>(
        pair<double, double>((a * (x1 - x0) + (y1 - y0) * sqrt(z * r0 * r0 - a * a)) / z + x0, 
                             (a * (y1 - y0) - (x1 - x0) * sqrt(z * r0 * r0 - a * a)) / z + y0),
        pair<double, double>((a * (x1 - x0) - (y1 - y0) * sqrt(z * r0 * r0 - a * a)) / z + x0, 
                             (a * (y1 - y0) + (x1 - x0) * sqrt(z * r0 * r0 - a * a)) / z + y0)
    );
}

int main()
{
    int n, k;
    cin >> n >> k;
    double x[100], y[100], c[100];
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> c[i];
    double left = 0, right = 1e8;
    while(right - left > right * 1e-8 && right - left > 1e-12){
        double mid = (right + left) / 2;
        bool f = false;
        for(int i = 0; i < n; i++){
            int d = 0;
            for(int j = 0; j < n; j++){
                if((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]) - right * 1e-8 < (mid / c[j]) * (mid / c[j])) d++;
            }
            if(d >= k) f = true;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                PP p = circle_cross_point(x[i], y[i], mid / c[i], x[j], y[j], mid / c[j]);
                double u = p.first.first, v = p.first.second;
                int d = 0;
                for(int l = 0; l < n; l++){
                    if((x[l] - u) * (x[l] - u) + (y[l] - v) * (y[l] - v) - right * 1e-8 < (mid / c[l]) * (mid / c[l])) d++;
                }
                if(d >= k) f = true;
                u = p.second.first, v = p.second.second;
                d = 0;
                for(int l = 0; l < n; l++){
                    if((x[l] - u) * (x[l] - u) + (y[l] - v) * (y[l] - v) - right * 1e-8 < (mid / c[l]) * (mid / c[l])) d++;
                }
                if(d >= k) f = true;
            }
        }
        if(f) right = mid;
        else left = mid;
    }
    cout << fixed << setprecision(15) << right << endl;
}