#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

double calc_dist(pair<double, double> p1, pair<double, double> p2){

  double dx = p1.first - p2.first;
  double dy = p1.second - p2.second;
  return sqrt(dx*dx + dy*dy);
};

int N, K;
vector<pair<double, double>> p;
vector<double> c;

int calc_cost(double x, double y, double T){

  int res = 0;

  for(int i = 0; i < N; i++){
      if(c[i] * calc_dist(make_pair(x, y), p[i]) <= T + 1e-9) res++;
  }
  return res;
}

const double one = 1.0 + 1e-11;
const double eps = 1e-8;

bool ok(double time){

  for(int i = 0; i < N; i++){
    if(calc_cost(p[i].first, p[i].second, time) >= K) return true;
  }

  for(int i = 0; i < N-1; i++){
    for(int j = i+1; j < N; j++){

      // ２つの交点
      // iの半径
      double r1 = time / c[i];
      double r2 = time / c[j];

      double x1 = p[i].first;
      double y1 = p[i].second;
      double x2 = p[j].first;
      double y2 = p[j].second;
      
      double d = sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));

      if(r1+r2<d) continue;
      if(r1+d<r2) continue;
      if(d+r2<r1) continue;
      double s=(r1+r2+d)/2;
      double a=sqrt(s*(s-r1)*(s-r2)*(s-d));
      double h=a/d*2;
      double d2=sqrt(r1*r1-h*h);
      double dx1=(x2-x1)/d;
      double dy1=(y2-y1)/d;
      double dx2=dy1;
      double dy2=-dx1;
      for(int cx=-1;cx<=1;cx+=2) {
        for(int cy=-1;cy<=1;cy+=2) {
          double tx=x1+cx*d2*dx1+cy*h*dx2;
          double ty=y1+cx*d2*dy1+cy*h*dy2;
          if(calc_cost(tx,ty,time)>=K) return 1;
        }
      }
    }
  }

  return false;
}


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> K;

  double x, y, tc;
  for(int i = 0; i < N; i++){
    cin >> x >> y >> tc;
    p.push_back(make_pair(x, y));
    c.push_back(tc);
  }

  double left = 0;
  double right = 1e9;

  while(right - left > 1e-10){

    double mid = (left + right) / 2.0;

    if(ok(mid)){
      right = mid;
    }else{
      left = mid;
    }

  }

  cout << setprecision(16) << right << endl;


  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

double calc_dist(pair<double, double> p1, pair<double, double> p2){

  double dx = p1.first - p2.first;
  double dy = p1.second - p2.second;
  return sqrt(dx*dx + dy*dy);
};

int N, K;
vector<pair<double, double>> p;
vector<double> c;

int calc_cost(double x, double y, double T){

  int res = 0;

  for(int i = 0; i < N; i++){
      if(c[i] * calc_dist(make_pair(x, y), p[i]) <= T + 1e-9) res++;
  }
  return res;
}

const double one = 1.0 + 1e-11;
const double eps = 1e-8;

bool ok(double time){

  for(int i = 0; i < N; i++){
    if(calc_cost(p[i].first, p[i].second, time) >= K) return true;
  }

  for(int i = 0; i < N-1; i++){
    for(int j = i+1; j < N; j++){

      // ２つの交点
      // iの半径
      double r1 = time / c[i];
      double r2 = time / c[j];

      double x1 = p[i].first;
      double y1 = p[i].second;
      double x2 = p[j].first;
      double y2 = p[j].second;
      
      double d = sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));

      if(r1+r2<d) continue;
      if(r1+d<r2) continue;
      if(d+r2<r1) continue;
      double s=(r1+r2+d)/2;
      double a=sqrt(s*(s-r1)*(s-r2)*(s-d));
      double h=a/d*2;
      double d2=sqrt(r1*r1-h*h);
      double dx1=(x2-x1)/d;
      double dy1=(y2-y1)/d;
      double dx2=dy1;
      double dy2=-dx1;
      for(int cx=-1;cx<=1;cx+=2) {
        for(int cy=-1;cy<=1;cy+=2) {
          double tx=x1+cx*d2*dx1+cy*h*dx2;
          double ty=y1+cx*d2*dy1+cy*h*dy2;
          if(calc_cost(tx,ty,time)>=K) return 1;
        }
      }
    }
  }

  return false;
}


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> K;

  double x, y, tc;
  for(int i = 0; i < N; i++){
    cin >> x >> y >> tc;
    p.push_back(make_pair(x, y));
    c.push_back(tc);
  }

  double left = 0;
  double right = 1e9;

  while(right - left > 1e-10){

    double mid = (left + right) / 2.0;

    if(ok(mid)){
      right = mid;
    }else{
      left = mid;
    }

  }

  cout << setprecision(16) << right << endl;


  return 0;
}

```