#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>

int const MAXN = 60;

int N, K, x[MAXN], y[MAXN], c[MAXN];


bool can_do(double X, double Y, double T) {
  int count = 0;
  for(int i = 0; i < N; ++i) {
    double xx = X - x[i], yy = Y - y[i];
    if((xx*xx+yy*yy)*c[i]*c[i]/(T*T) <= 1+1e-12) ++count;
    if(count >= K) return true;
  }
  return false;
}

double calc_intersect(double x, double y, double r1, double r2,
  double& X, double& Y, double& dx, double&dy) {
  double l2 = x*x + y*y;
  double a2 = (l2 + r1*r1-r2*r2)*0.5;
  double det = l2*r1*r1 - a2*a2;
  if(det < 0) return det;
  double t2 = std::sqrt(det);
  X = a2*x/l2; Y = a2*y/l2;
  dx = y*t2/l2; dy = -x*t2/l2;
  return det;
}

bool can_do(double T) {
  for(int i = 0; i < N; ++i) {
    if(can_do(x[i], y[i], T)) return true;
  }
  for(int i = 0; i < N-1; ++i) for(int j = i+1; j < N; ++j) {
    double X, Y, dx, dy;
    if(calc_intersect(x[j]-x[i], y[j]-y[i], T/c[i], T/c[j], X, Y, dx, dy)< 0e0) continue;
    X += x[i];
    Y += y[i];
    if(can_do(X+dx, Y+dy, T)) return true;
    if(can_do(X-dx, Y-dy, T)) return true;
  }
  return false;
}

int main() {
  std::cin >> N >> K;
  for(int i = 0; i < N; ++i) std::cin >> x[i] >> y[i] >> c[i];
  double tL = 0, tH = 150*1000; // > 1000*sqrt(2)*100
  while(tH - tL > 1e-10) {
    double tM = (tL + tH)*0.5;
    if(can_do(tM)) tH = tM; else tL = tM;
  }
  std::cout << std::setprecision(10) << std::fixed << (tL+tH)*0.5 << std::endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>

int const MAXN = 60;

int N, K, x[MAXN], y[MAXN], c[MAXN];


bool can_do(double X, double Y, double T) {
  int count = 0;
  for(int i = 0; i < N; ++i) {
    double xx = X - x[i], yy = Y - y[i];
    if((xx*xx+yy*yy)*c[i]*c[i]/(T*T) <= 1+1e-12) ++count;
    if(count >= K) return true;
  }
  return false;
}

double calc_intersect(double x, double y, double r1, double r2,
  double& X, double& Y, double& dx, double&dy) {
  double l2 = x*x + y*y;
  double a2 = (l2 + r1*r1-r2*r2)*0.5;
  double det = l2*r1*r1 - a2*a2;
  if(det < 0) return det;
  double t2 = std::sqrt(det);
  X = a2*x/l2; Y = a2*y/l2;
  dx = y*t2/l2; dy = -x*t2/l2;
  return det;
}

bool can_do(double T) {
  for(int i = 0; i < N; ++i) {
    if(can_do(x[i], y[i], T)) return true;
  }
  for(int i = 0; i < N-1; ++i) for(int j = i+1; j < N; ++j) {
    double X, Y, dx, dy;
    if(calc_intersect(x[j]-x[i], y[j]-y[i], T/c[i], T/c[j], X, Y, dx, dy)< 0e0) continue;
    X += x[i];
    Y += y[i];
    if(can_do(X+dx, Y+dy, T)) return true;
    if(can_do(X-dx, Y-dy, T)) return true;
  }
  return false;
}

int main() {
  std::cin >> N >> K;
  for(int i = 0; i < N; ++i) std::cin >> x[i] >> y[i] >> c[i];
  double tL = 0, tH = 150*1000; // > 1000*sqrt(2)*100
  while(tH - tL > 1e-10) {
    double tM = (tL + tH)*0.5;
    if(can_do(tM)) tH = tM; else tL = tM;
  }
  std::cout << std::setprecision(10) << std::fixed << (tL+tH)*0.5 << std::endl;
  return 0;
}

```