#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

typedef complex<double> P;
namespace std{bool operator<(const P& a, const P& b){
  return real(a)!=real(b)?real(a)<real(b):imag(a)<imag(b);
}}
struct C{
  P p; double r;
  C(const P& p, double r):p(p),r(r){}
};

pair<P,P> cc_cross(const C& c1, const C& c2){
  double d = abs(c1.p - c2.p);
  double rc = (d*d+c1.r*c1.r - c2.r*c2.r) / (2*d);
  double rs = sqrt(c1.r*c1.r - rc*rc);
  P diff = (c2.p - c1.p) / d;
  return make_pair(c1.p+diff*P(rc,rs), c1.p + diff*P(rc,-rs));
}


static const double EPS = 1e-8;

// K枚以上か
bool check(double X, const vector<vector<int>>& v, int K){
  vector<P> cand;
  rep(i,v.size()){
    P p1(v[i][0], v[i][1]);
    double d1 = X/v[i][2];

    cand.push_back(p1);
    rep(j,v.size()){
      
      P p2(v[j][0], v[j][1]);
      double d2 = X/v[j][2];

      C c1(p1, d1);
      C c2(p2, d2);

      if(abs(p1-p2) < d1+d2+EPS){
        pair<P,P> res = cc_cross(c1,c2);
        cand.push_back(res.first);
        cand.push_back(res.second);
      }
    }
  }

  bool ret = false;
  rep(i,cand.size()){
    P p = cand[i];
    //cerr << real(p) << " " << imag(p) << endl;
    int cnt = 0;
    rep(j,v.size()){
      P p1(v[j][0], v[j][1]);
      double d1 = X/v[j][2];
      double dist = abs(p-p1);
      //cerr << "  " << d1 << " " << dist << endl;
      
      if(d1+EPS>dist) cnt++;
    }
    //cerr << "   " << cnt << " " << K << endl;
    if(cnt >= K) ret = true;

  }
  //cerr << X << "\t" << (ret?"OK":"NG") << endl;
  return ret;
}

int main(){
  int N, K;
  cin >> N >> K;
  vector<vector<int>> v;
  rep(i,N){
    int x, y, c;
    cin >> x >> y >> c;
    v.push_back({x,y,c});
  }

  double lb = 0.0, ub = 1e20;
  rep(i,150){
    double mid = (lb+ub)/2.0;
    if(!check(mid, v, K)) lb = mid;
    else ub = mid;
  }

  printf("%.12lf\n", ub);
  
  return 0;
}

### Prompt

Please formulate a CPP solution to 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 REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

typedef complex<double> P;
namespace std{bool operator<(const P& a, const P& b){
  return real(a)!=real(b)?real(a)<real(b):imag(a)<imag(b);
}}
struct C{
  P p; double r;
  C(const P& p, double r):p(p),r(r){}
};

pair<P,P> cc_cross(const C& c1, const C& c2){
  double d = abs(c1.p - c2.p);
  double rc = (d*d+c1.r*c1.r - c2.r*c2.r) / (2*d);
  double rs = sqrt(c1.r*c1.r - rc*rc);
  P diff = (c2.p - c1.p) / d;
  return make_pair(c1.p+diff*P(rc,rs), c1.p + diff*P(rc,-rs));
}


static const double EPS = 1e-8;

// K枚以上か
bool check(double X, const vector<vector<int>>& v, int K){
  vector<P> cand;
  rep(i,v.size()){
    P p1(v[i][0], v[i][1]);
    double d1 = X/v[i][2];

    cand.push_back(p1);
    rep(j,v.size()){
      
      P p2(v[j][0], v[j][1]);
      double d2 = X/v[j][2];

      C c1(p1, d1);
      C c2(p2, d2);

      if(abs(p1-p2) < d1+d2+EPS){
        pair<P,P> res = cc_cross(c1,c2);
        cand.push_back(res.first);
        cand.push_back(res.second);
      }
    }
  }

  bool ret = false;
  rep(i,cand.size()){
    P p = cand[i];
    //cerr << real(p) << " " << imag(p) << endl;
    int cnt = 0;
    rep(j,v.size()){
      P p1(v[j][0], v[j][1]);
      double d1 = X/v[j][2];
      double dist = abs(p-p1);
      //cerr << "  " << d1 << " " << dist << endl;
      
      if(d1+EPS>dist) cnt++;
    }
    //cerr << "   " << cnt << " " << K << endl;
    if(cnt >= K) ret = true;

  }
  //cerr << X << "\t" << (ret?"OK":"NG") << endl;
  return ret;
}

int main(){
  int N, K;
  cin >> N >> K;
  vector<vector<int>> v;
  rep(i,N){
    int x, y, c;
    cin >> x >> y >> c;
    v.push_back({x,y,c});
  }

  double lb = 0.0, ub = 1e20;
  rep(i,150){
    double mid = (lb+ub)/2.0;
    if(!check(mid, v, K)) lb = mid;
    else ub = mid;
  }

  printf("%.12lf\n", ub);
  
  return 0;
}

```