#include <bits/stdc++.h>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}

using comp = std::complex<double>;

signed main(){
    int n, k;
    cin >> n >> k;
    
    vector<comp> center(n);
    vector<int> weight(n);
    REP(i, n){
        double a, b, c;
        cin >> a >> b >> c;
        center[i] = comp(a, b);
        weight[i] = c;
    }

    double ng = 0, ok = 1e7;
    const double eps = 1e-8;

    while(ok - ng > eps){
        double mid = (ok + ng) / 2;
        vector<comp> intersection(center);

        REP(i, n-1){
            FOR(j, i+1, n){
                const comp& c1 = center[i], c2 = center[j];
                comp c12 = c2 - c1;

                double r1 = mid / weight[i], r2 = mid / weight[j];

                double a = abs(c12);
                double d = (a*a + r1*r1 - r2*r2) / (2.0 * a);

                if(r1 + r2 < a - eps || abs(r1 - r2) > a + eps) continue;

                double h = sqrt(r1*r1 - d*d);

                comp c3 = (c12 / a) * d;

                intersection.emplace_back(c1 + c3 + (c12 / a) * comp(0, h));
                intersection.emplace_back(c1 + c3 + (c12 / a) * comp(0, -h));
            }
        }

        bool enclose = false;

        for(const auto& i : intersection) {
            int cnt = 0;
            REP(j, n){
                double r = mid / weight[j];
                cnt += abs(i - center[j]) <= r + eps;
            }
            if(cnt >= k){
                enclose = true;
            }
        }

        if(enclose) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    cout << setprecision(12) << ok << endl;
    
    return 0;
}

### Prompt

Create a solution in Cpp for the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}

using comp = std::complex<double>;

signed main(){
    int n, k;
    cin >> n >> k;
    
    vector<comp> center(n);
    vector<int> weight(n);
    REP(i, n){
        double a, b, c;
        cin >> a >> b >> c;
        center[i] = comp(a, b);
        weight[i] = c;
    }

    double ng = 0, ok = 1e7;
    const double eps = 1e-8;

    while(ok - ng > eps){
        double mid = (ok + ng) / 2;
        vector<comp> intersection(center);

        REP(i, n-1){
            FOR(j, i+1, n){
                const comp& c1 = center[i], c2 = center[j];
                comp c12 = c2 - c1;

                double r1 = mid / weight[i], r2 = mid / weight[j];

                double a = abs(c12);
                double d = (a*a + r1*r1 - r2*r2) / (2.0 * a);

                if(r1 + r2 < a - eps || abs(r1 - r2) > a + eps) continue;

                double h = sqrt(r1*r1 - d*d);

                comp c3 = (c12 / a) * d;

                intersection.emplace_back(c1 + c3 + (c12 / a) * comp(0, h));
                intersection.emplace_back(c1 + c3 + (c12 / a) * comp(0, -h));
            }
        }

        bool enclose = false;

        for(const auto& i : intersection) {
            int cnt = 0;
            REP(j, n){
                double r = mid / weight[j];
                cnt += abs(i - center[j]) <= r + eps;
            }
            if(cnt >= k){
                enclose = true;
            }
        }

        if(enclose) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    cout << setprecision(12) << ok << endl;
    
    return 0;
}

```