#include <bits/stdc++.h>
using namespace std;
const double INF = 1000000;
const double EPS = 0.000000001;
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator +(point P){
    return point(x + P.x, y + P.y);
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
  point operator *(double k){
    return point(x * k, y * k);
  }
  point operator /(double k){
    return point(x / k, y / k);
  }
};
double abs(point P){
  return sqrt(pow(P.x, 2) + pow(P.y, 2));
}
double dist(point P, point Q){
  return abs(Q - P);
}
point rotate90(point P){
  return point(P.y, - P.x);
}
struct circle{
  point C;
  double r;
  circle(){
  }
  circle(point C, double r): C(C), r(r){
  }
};
bool in_circle(point P, circle C){
  return dist(P, C.C) <= C.r + EPS;
}
pair<point, point> circle_intersection(circle C1, circle C2){
  double d = dist(C1.C, C2.C);
  double x = (C1.r * C1.r - C2.r * C2.r + d * d) / (2 * d);
  point A = C1.C + (C2.C - C1.C) / d * x;
  double y = sqrt(C1.r * C1.r - x * x);
  point B = rotate90(C2.C - C1.C) / d * y;
  return make_pair(A + B, A - B);
}
int main(){
  cout << fixed << setprecision(10);
  int N, K;
  cin >> N >> K;
  vector<point> P(N);
  vector<double> c(N);
  for (int i = 0; i < N; i++){
    cin >> P[i].x >> P[i].y >> c[i];
  }
  double t = INF;
  double f = 0;
  for (int i = 0; i < 100; i++){
    double mid = (t + f) / 2;
    vector<circle> C(N);
    for (int j = 0; j < N; j++){
      C[j] = circle(P[j], mid / c[j]);
    }
    vector<point> Q;
    for (int j = 0; j < N; j++){
      Q.push_back(P[j]);
    }
    for (int j = 0; j < N; j++){
      for (int k = j + 1; k < N; k++){
        double d = dist(C[j].C, C[k].C);
        if (abs(C[j].r - C[k].r) <= d && d <= C[j].r + C[k].r){
          pair<point, point> tmp = circle_intersection(C[j], C[k]);
          Q.push_back(tmp.first);
          Q.push_back(tmp.second);
        }
      }
    }
    int cnt = Q.size();
    bool ok = false;
    for (int j = 0; j < cnt; j++){
      int cnt2 = 0;
      for (int k = 0; k < N; k++){
        if (in_circle(Q[j], C[k])){
          cnt2++;
        }
      }
      if (cnt2 >= K){
        ok = true;
      }
    }
    if (ok){
      t = mid;
    } else {
      f = mid;
    }
  }
  cout << t << endl;
}
### Prompt

Please create a solution in CPP 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;
const double INF = 1000000;
const double EPS = 0.000000001;
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator +(point P){
    return point(x + P.x, y + P.y);
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
  point operator *(double k){
    return point(x * k, y * k);
  }
  point operator /(double k){
    return point(x / k, y / k);
  }
};
double abs(point P){
  return sqrt(pow(P.x, 2) + pow(P.y, 2));
}
double dist(point P, point Q){
  return abs(Q - P);
}
point rotate90(point P){
  return point(P.y, - P.x);
}
struct circle{
  point C;
  double r;
  circle(){
  }
  circle(point C, double r): C(C), r(r){
  }
};
bool in_circle(point P, circle C){
  return dist(P, C.C) <= C.r + EPS;
}
pair<point, point> circle_intersection(circle C1, circle C2){
  double d = dist(C1.C, C2.C);
  double x = (C1.r * C1.r - C2.r * C2.r + d * d) / (2 * d);
  point A = C1.C + (C2.C - C1.C) / d * x;
  double y = sqrt(C1.r * C1.r - x * x);
  point B = rotate90(C2.C - C1.C) / d * y;
  return make_pair(A + B, A - B);
}
int main(){
  cout << fixed << setprecision(10);
  int N, K;
  cin >> N >> K;
  vector<point> P(N);
  vector<double> c(N);
  for (int i = 0; i < N; i++){
    cin >> P[i].x >> P[i].y >> c[i];
  }
  double t = INF;
  double f = 0;
  for (int i = 0; i < 100; i++){
    double mid = (t + f) / 2;
    vector<circle> C(N);
    for (int j = 0; j < N; j++){
      C[j] = circle(P[j], mid / c[j]);
    }
    vector<point> Q;
    for (int j = 0; j < N; j++){
      Q.push_back(P[j]);
    }
    for (int j = 0; j < N; j++){
      for (int k = j + 1; k < N; k++){
        double d = dist(C[j].C, C[k].C);
        if (abs(C[j].r - C[k].r) <= d && d <= C[j].r + C[k].r){
          pair<point, point> tmp = circle_intersection(C[j], C[k]);
          Q.push_back(tmp.first);
          Q.push_back(tmp.second);
        }
      }
    }
    int cnt = Q.size();
    bool ok = false;
    for (int j = 0; j < cnt; j++){
      int cnt2 = 0;
      for (int k = 0; k < N; k++){
        if (in_circle(Q[j], C[k])){
          cnt2++;
        }
      }
      if (cnt2 >= K){
        ok = true;
      }
    }
    if (ok){
      t = mid;
    } else {
      f = mid;
    }
  }
  cout << t << endl;
}
```