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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;
const static double eps = 1e-9;
bool equal(const double& a, const double& b) {
  return abs(a - b) < eps;
}

struct tensor {
  vector<double> v;
  size_t n;
  
  tensor(){}
  tensor(const vector<double>& vec) {
    v = vec;
    n = vec.size();
  }
  tensor(const tensor& t) {
    v = t.v;
    n = t.n;
  }
  
  tensor operator+(const tensor& t) const {
    assert(n == t.n);
    vector<double> nv(v);
    for (int i = 0; i < n; ++i) nv[i] += t.v[i];
    return tensor(nv);
  }
  
  tensor operator-(const tensor& t) const {
    assert(n == t.n);
    vector<double> nv(v);
    for (int i = 0; i < n; ++i) nv[i] -= t.v[i];
    return tensor(nv);
  }
  
  tensor operator*(const double& a) const {
    vector<double> nv(v);
    for (int i = 0; i < n; ++i) nv[i] *= a;
    return tensor(nv);
  }
  
  double norm() const {
    double s(0.0);
    for (int i = 0; i < n; ++i) s += v[i] * v[i];
    return sqrt(s);
  }
  
  void rect_rotate() { // only for 2d
    assert(n == 2);
    swap(v[0], v[1]);
    v[0] *= -1;
  }
};

struct circle {
  tensor o;
  double r;
  
  circle(){
  	o.v.resize(2);
    o.n = 2;
  }
  circle(const tensor& origin, const double& radius) {
    o = origin;
    r = radius;
  }
  circle(const circle& c) {
    o = c.o;
    r = c.r;
  }
  
  vector<tensor> intersect(const circle& c) const {
    tensor v(c.o-o);
    double d(v.norm());
    if (equal(d, 0)) return {};
    double d1(d+r+c.r), d2(max(d, max(r, c.r)));
    if (equal(d1, d2)) return {o + v * (r / d)};
    if (d1 < d2) return {};
    double x((r*r+d*d-c.r*c.r) / (2*d)), y(sqrt(r*r-x*x));
    tensor mid(o + v * (x/d));
    v.rect_rotate();
    return {mid + v * (y / d), mid - v * (y / d)};
  }
  
  bool inside(const tensor& v) const {
    return (v-o).norm() < r + eps;
  }
};

int main() {
  int n, k;
  cin >> n >> k;
  
  vector<circle> cs(n);
  for (int i = 0; i < n; ++i)
    cin >> cs[i].o.v[0] >> cs[i].o.v[1] >> cs[i].r;
  
  double min_t(0), max_t(400000);
  while (!equal(min_t, max_t)) {
    double mid_t((min_t + max_t) / 2);
    
    vector<circle> tcs(cs);
    for (circle& c: tcs) c.r = mid_t / c.r;
    
    vector<tensor> points;
    for (int i = 0; i < n; ++i) {
      points.push_back(cs[i].o);
      for (int j = 0; j < i; ++j) {
        vector<tensor> temp = tcs[i].intersect(tcs[j]);
        points.insert(points.end(), temp.begin(), temp.end());
      }
    }
    
    bool found(false);
    for (tensor p: points) {
      int cnt(0);
      for (int i = 0; i < n; ++i) cnt += tcs[i].inside(p);
      if (cnt >= k) {
        found = true;
        break;
      }
    }
    found ? max_t = mid_t : min_t = mid_t;
  }
  printf("%.10f\n", min_t);
  return 0;
}