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 <algorithm>
#include <iostream>
#include <complex>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
using namespace std;
using W = double;
using P = complex<W>;
using L = pair<P,P>;
using C = pair<P,W>;
using Poly = vector<P>;
#define X real()
#define Y imag()
const W EPS = (1e-10), pi = acos(-1);

//円と円の交点
vector<P> cpcc(C a, C b){
  P ca = a.first, cb = b.first;
  W d = abs(ca-cb), ra = a.second, rb = b.second;
  W t = (ra*ra-rb*rb+d*d)/2/d, h = sqrt(ra*ra-t*t);
  P m = t/abs(cb-ca)*(cb-ca)+ca;
  vector<P> cp(2,m);
  P n = (ca-cb)*P(0,1);
  n *= h/abs(n);
  cp[0] -= n;
  cp[1] += n;
  return cp;
}

int main(){
  int N, K;
  cin >> N >> K;
  vector<P> Center;
  vector<W> Ci;
  for(int i = 0; i < N; ++i){
    double x, y, c;
    cin >> x >> y >> c;
    Center.emplace_back(x,y);
    Ci.emplace_back(c);
  }
  double ng = 0, ok = 1e9;
  for(int itr = 0; itr < 100; ++itr){
    double m = (ok+ng)/2;
    vector<C> M;
    for(int i = 0; i < N; ++i){
      M.push_back(C(Center[i],m/Ci[i]));
    }
    vector<P> cand = Center;
    for(int i = 0; i < N; ++i){
      for(int j = 0; j < i; ++j){
        double d = abs(M[i].first-M[j].first);
        double ri = M[i].second, rj = M[j].second;
        if(d < ri+rj-EPS and d > abs(ri-rj)+EPS){
          auto tmp = cpcc(M[i],M[j]);
          for(auto p : tmp)
            cand.emplace_back(p);
        }
      }
    }
    bool f = false;
    for(auto p : cand){
      int cnt = 0;
      for(auto c : M){
        if(abs(c.first-p) < c.second+EPS)
          ++cnt;
      }
      if(cnt >= K){
        f = true;
        break;
      }
    }
    if(f) ok = m;
    else ng = m;
  }
  printf("%.12f\n",ok);
}