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

#define EPS (1e-9)
#define EQ(a, b) (abs((a) - (b)) < EPS)

typedef complex<double> Vector2;

double dot(Vector2 a, Vector2 b) { return real(conj(a) * b); }
double cross(Vector2 a, Vector2 b) { return imag(conj(a) * b); }

vector<Vector2> CircleIntersections(Vector2 a, Vector2 b, double ra, double rb) {
  double d = abs(b - a);
  if (ra + rb < d) return {};
  double c = acos((ra * ra + d * d - rb * rb) / (2 * ra * d));
  double t = atan2(b.imag() - a.imag(), b.real() - a.real());
  Vector2 p1 = a + Vector2(cos(t + c) * ra, sin(t + c) * ra);
  Vector2 p2 = a + Vector2(cos(t - c) * ra, sin(t - c) * ra);
  return {p1, p2};
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<Vector2> v(n);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y >> c[i];
    v[i] = Vector2(x, y);
  }
  if (k == 1) {
    cout << 0 << endl;
    return 0;
  }

  double a = 1e9;
  for (int top0 = 1; top0 < 1e9; top0 *= 10) {
    double bot = 0, top = top0, mid;
    while (!EQ(bot, top)) {
      mid = bot + (top - bot) / 2;
      bool valid = false;
      for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
          auto u = CircleIntersections(v[i], v[j], mid / c[i], mid / c[j]);
          //
          if (!u.empty()) u.push_back((u[0] + u[1]) / 2.0);
          //
          for (auto e : u) {
            int x = 2;
            for (int l = 0; l < n; l++) {
              if (l == i || l == j) continue;
              x += abs(e - v[l]) <= mid / c[l];
            }
            if (x >= k) valid = true;
          }
        }
      }
      if (valid) {
        top = mid;
      } else {
        bot = mid;
      }
    }
    if (!EQ(top, top0)) a = min(a, bot);
  }
  cout << fixed << setprecision(9);
  cout << a << endl;
}

### Prompt

In Cpp, your task is to solve 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 EPS (1e-9)
#define EQ(a, b) (abs((a) - (b)) < EPS)

typedef complex<double> Vector2;

double dot(Vector2 a, Vector2 b) { return real(conj(a) * b); }
double cross(Vector2 a, Vector2 b) { return imag(conj(a) * b); }

vector<Vector2> CircleIntersections(Vector2 a, Vector2 b, double ra, double rb) {
  double d = abs(b - a);
  if (ra + rb < d) return {};
  double c = acos((ra * ra + d * d - rb * rb) / (2 * ra * d));
  double t = atan2(b.imag() - a.imag(), b.real() - a.real());
  Vector2 p1 = a + Vector2(cos(t + c) * ra, sin(t + c) * ra);
  Vector2 p2 = a + Vector2(cos(t - c) * ra, sin(t - c) * ra);
  return {p1, p2};
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<Vector2> v(n);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y >> c[i];
    v[i] = Vector2(x, y);
  }
  if (k == 1) {
    cout << 0 << endl;
    return 0;
  }

  double a = 1e9;
  for (int top0 = 1; top0 < 1e9; top0 *= 10) {
    double bot = 0, top = top0, mid;
    while (!EQ(bot, top)) {
      mid = bot + (top - bot) / 2;
      bool valid = false;
      for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
          auto u = CircleIntersections(v[i], v[j], mid / c[i], mid / c[j]);
          //
          if (!u.empty()) u.push_back((u[0] + u[1]) / 2.0);
          //
          for (auto e : u) {
            int x = 2;
            for (int l = 0; l < n; l++) {
              if (l == i || l == j) continue;
              x += abs(e - v[l]) <= mid / c[l];
            }
            if (x >= k) valid = true;
          }
        }
      }
      if (valid) {
        top = mid;
      } else {
        bot = mid;
      }
    }
    if (!EQ(top, top0)) a = min(a, bot);
  }
  cout << fixed << setprecision(9);
  cout << a << endl;
}

```