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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;

long long MOD = 1000000000 + 7;

vector<double> x,y,c;
vector<pdd> v;
int N,K;
double EPS = 0.0000001;

vector<pdd> getIntersection(double x0, double y0, double r0, double x1, double y1, double r1){
  x1 -= x0;
  y1 -= y0;

  vector<pdd> ret;
  double x_p, x_n, y_p, y_n;

  double a = 2 * x1;
  double b = 2 * y1;
  double c = x1*x1 + y1*y1 - r1*r1 + r0*r0;

  double D = b*b * (a*a*r0*r0 + b * b * r0*r0 - c * c);

  if(D < 0){
    return ret;
  }

  if(b==0){
    x_p = c / a;
    x_n = c / a;
    y_p = r0 * r0 - x_p*x_p;
    y_p = pow(y_p, 0.5);
    y_n = -y_p;
  } else {
    D = pow(D, 0.5);
    x_p = a * c + D;
    x_p /= a*a + b*b;
    x_n = a * c - D;
    x_n /= a*a + b*b;

    y_p = -a * x_p + c;
    y_p /= b;
    y_n = -a * x_n + c;
    y_n /= b;
  }

  pdd tmp1,tmp2;
  tmp1 = make_pair(x_p + x0, y_p + y0);
  tmp2 = make_pair(x_n + x0, y_n + y0);
  ret = {tmp1, tmp2};
  return ret;
}

bool isOK(double t){
  int index = N;
  // cerr << "candidate: " << v.size() << endl;

  for(int i = 0; i < N-1; i++){
    for(int j = i+1; j < N; j++){
      auto tmp = getIntersection(x[i], y[i], t/c[i], x[j], y[j], t/c[j]);
      if(tmp.size() > 0){
        v[index] = tmp[0];
        v[index+1] = tmp[1];
        index+=2;
      }
    }
  }
  // cerr << "candidate: " << v.size() << endl;

  for(int i = 0; i < index; i++){
    // K個以上の点からの距離がc[i]/t以下ならOK
    double xtmp = v[i].first;
    double ytmp = v[i].second;
    int k = 0;
    for(int i = 0; i < N; i++){
      double d = 0;
      d += (x[i] -xtmp) * (x[i]-xtmp);
      d += (y[i] -ytmp) * (y[i]-ytmp);
      double r = t * t / c[i] / c[i];
      if(d - r < EPS) {
        // cerr << x[i] << " " << y[i] << " " << t / c[i] <<  " " << d << endl;
        k++;
        if(k>=K) return true; 
      }
    }
  }

  return false;

}



int main(){
  cout << setprecision(10);
  cin >> N >> K;
  x.assign(N,0);
  y.assign(N,0);
  c.assign(N,0);
  pdd tmp;
  v.assign(N*N, tmp);
  for(int i = 0; i < N; i++){
    cin >> x[i] >> y[i] >> c[i];
    v[i] = make_pair(x[i], y[i]);
  }

  // cerr << (isOK(7422) ? "OK" : "NG" )  << endl;

  double right = 1000000;
  double left = EPS;
  double mid;
  while((right - left > EPS) || ( (right - left)/right > EPS)){
    // cerr << left << " " << right << endl;
    mid = (right + left) / 2.0;
    if(isOK(mid)){
      right = mid;
    } else { 
      left = mid;
    }
  }
  cout << right << endl;

}

### 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;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;

long long MOD = 1000000000 + 7;

vector<double> x,y,c;
vector<pdd> v;
int N,K;
double EPS = 0.0000001;

vector<pdd> getIntersection(double x0, double y0, double r0, double x1, double y1, double r1){
  x1 -= x0;
  y1 -= y0;

  vector<pdd> ret;
  double x_p, x_n, y_p, y_n;

  double a = 2 * x1;
  double b = 2 * y1;
  double c = x1*x1 + y1*y1 - r1*r1 + r0*r0;

  double D = b*b * (a*a*r0*r0 + b * b * r0*r0 - c * c);

  if(D < 0){
    return ret;
  }

  if(b==0){
    x_p = c / a;
    x_n = c / a;
    y_p = r0 * r0 - x_p*x_p;
    y_p = pow(y_p, 0.5);
    y_n = -y_p;
  } else {
    D = pow(D, 0.5);
    x_p = a * c + D;
    x_p /= a*a + b*b;
    x_n = a * c - D;
    x_n /= a*a + b*b;

    y_p = -a * x_p + c;
    y_p /= b;
    y_n = -a * x_n + c;
    y_n /= b;
  }

  pdd tmp1,tmp2;
  tmp1 = make_pair(x_p + x0, y_p + y0);
  tmp2 = make_pair(x_n + x0, y_n + y0);
  ret = {tmp1, tmp2};
  return ret;
}

bool isOK(double t){
  int index = N;
  // cerr << "candidate: " << v.size() << endl;

  for(int i = 0; i < N-1; i++){
    for(int j = i+1; j < N; j++){
      auto tmp = getIntersection(x[i], y[i], t/c[i], x[j], y[j], t/c[j]);
      if(tmp.size() > 0){
        v[index] = tmp[0];
        v[index+1] = tmp[1];
        index+=2;
      }
    }
  }
  // cerr << "candidate: " << v.size() << endl;

  for(int i = 0; i < index; i++){
    // K個以上の点からの距離がc[i]/t以下ならOK
    double xtmp = v[i].first;
    double ytmp = v[i].second;
    int k = 0;
    for(int i = 0; i < N; i++){
      double d = 0;
      d += (x[i] -xtmp) * (x[i]-xtmp);
      d += (y[i] -ytmp) * (y[i]-ytmp);
      double r = t * t / c[i] / c[i];
      if(d - r < EPS) {
        // cerr << x[i] << " " << y[i] << " " << t / c[i] <<  " " << d << endl;
        k++;
        if(k>=K) return true; 
      }
    }
  }

  return false;

}



int main(){
  cout << setprecision(10);
  cin >> N >> K;
  x.assign(N,0);
  y.assign(N,0);
  c.assign(N,0);
  pdd tmp;
  v.assign(N*N, tmp);
  for(int i = 0; i < N; i++){
    cin >> x[i] >> y[i] >> c[i];
    v[i] = make_pair(x[i], y[i]);
  }

  // cerr << (isOK(7422) ? "OK" : "NG" )  << endl;

  double right = 1000000;
  double left = EPS;
  double mid;
  while((right - left > EPS) || ( (right - left)/right > EPS)){
    // cerr << left << " " << right << endl;
    mid = (right + left) / 2.0;
    if(isOK(mid)){
      right = mid;
    } else { 
      left = mid;
    }
  }
  cout << right << endl;

}

```