#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

using Vect = pair<long double, long double>;

Vect operator+(Vect lhs, Vect rhs){
  Vect ret = make_pair(0, 0);
  ret.first = lhs.first + rhs.first;
  ret.second = lhs.second + rhs.second;
  return ret;
}
Vect operator-(Vect& lhs, Vect& rhs){
  Vect ret;
  ret.first = lhs.first - rhs.first;
  ret.second = lhs.second - rhs.second;
  return ret;
}

Vect operator*(long double lhs, const Vect& rhs){
  return make_pair(lhs * rhs.first, lhs * rhs.second);
}

long double norm(const Vect& v){
  return sqrt(v.first * v.first + v.second * v.second);
}

Vect rotate(Vect v, long double cost, long double sint){
  return make_pair(
                   v.first * cost - v.second * sint,
                   v.first * sint + v.second * cost
                   );
}

const long double EPS = 1e-12;

int main(){
  int N, K;
  cin >> N >> K;

  vector<pair<Vect, long double>> xyc(N);
  for(int i = 0; i < N; i++){
    long double x, y, c;
    cin >> x >> y >> c;
    xyc[i] = make_pair(make_pair(x, y), c);
  }

  long double ur = 1e7, lr = 0;
  for(int _ = 0; _ < 100; _++){
    //cout << lr << ' ' << ur << endl;
    long double mid = (lr + ur) / 2;
    vector<Vect> center_cands;

    for(auto v: xyc){
      center_cands.push_back(v.first);
    }

    for(auto m1: xyc){
      for(auto m2: xyc){
        long double r1 = mid / m1.second, r2 = mid / m2.second;
        long double l = norm(m1.first - m2.first);
        if(l < EPS){
          continue;
        }
        if((l <= r1 + r2) &&
           (l >= abs(r1 - r2))){
          long double cost = (r1 * r1 + l * l - r2 * r2) / (2 * r1 * l);
          long double sint = sqrt(1 - cost * cost);
          //cout << cost << ' ' << sint << endl;
          Vect diff = m2.first - m1.first;
          //          Vect diff_norm = (1 / l) * (m2.first - m1.first);
          Vect v1 = m1.first + (r1 / l) * rotate(diff, cost, sint);
          Vect v2 = m1.first + (r1 / l) * rotate(diff, cost, -sint);
          center_cands.push_back(v1);
          center_cands.push_back(v2);
        }
      }
    }
    /*
    for(auto c: center_cands){
    cout << '(' << c.first << ',' << c.second << ')' << ' ';
    }cout << endl;
    */

    int max_cnt = 0;
    for(auto center: center_cands){
      int cnt = 0;
      for(auto p: xyc){
        long double dist = norm(center - p.first) * p.second;
        if(dist <= mid + EPS){
          cnt++;
        }
      }
      max_cnt = max(max_cnt, cnt);
    }
    //cout << max_cnt << endl;
    if(max_cnt >= K){
      ur = mid;
    }else{
      lr = mid;
    }
  }
  cout << setprecision(20) << (lr + ur) / 2 << 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<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

using Vect = pair<long double, long double>;

Vect operator+(Vect lhs, Vect rhs){
  Vect ret = make_pair(0, 0);
  ret.first = lhs.first + rhs.first;
  ret.second = lhs.second + rhs.second;
  return ret;
}
Vect operator-(Vect& lhs, Vect& rhs){
  Vect ret;
  ret.first = lhs.first - rhs.first;
  ret.second = lhs.second - rhs.second;
  return ret;
}

Vect operator*(long double lhs, const Vect& rhs){
  return make_pair(lhs * rhs.first, lhs * rhs.second);
}

long double norm(const Vect& v){
  return sqrt(v.first * v.first + v.second * v.second);
}

Vect rotate(Vect v, long double cost, long double sint){
  return make_pair(
                   v.first * cost - v.second * sint,
                   v.first * sint + v.second * cost
                   );
}

const long double EPS = 1e-12;

int main(){
  int N, K;
  cin >> N >> K;

  vector<pair<Vect, long double>> xyc(N);
  for(int i = 0; i < N; i++){
    long double x, y, c;
    cin >> x >> y >> c;
    xyc[i] = make_pair(make_pair(x, y), c);
  }

  long double ur = 1e7, lr = 0;
  for(int _ = 0; _ < 100; _++){
    //cout << lr << ' ' << ur << endl;
    long double mid = (lr + ur) / 2;
    vector<Vect> center_cands;

    for(auto v: xyc){
      center_cands.push_back(v.first);
    }

    for(auto m1: xyc){
      for(auto m2: xyc){
        long double r1 = mid / m1.second, r2 = mid / m2.second;
        long double l = norm(m1.first - m2.first);
        if(l < EPS){
          continue;
        }
        if((l <= r1 + r2) &&
           (l >= abs(r1 - r2))){
          long double cost = (r1 * r1 + l * l - r2 * r2) / (2 * r1 * l);
          long double sint = sqrt(1 - cost * cost);
          //cout << cost << ' ' << sint << endl;
          Vect diff = m2.first - m1.first;
          //          Vect diff_norm = (1 / l) * (m2.first - m1.first);
          Vect v1 = m1.first + (r1 / l) * rotate(diff, cost, sint);
          Vect v2 = m1.first + (r1 / l) * rotate(diff, cost, -sint);
          center_cands.push_back(v1);
          center_cands.push_back(v2);
        }
      }
    }
    /*
    for(auto c: center_cands){
    cout << '(' << c.first << ',' << c.second << ')' << ' ';
    }cout << endl;
    */

    int max_cnt = 0;
    for(auto center: center_cands){
      int cnt = 0;
      for(auto p: xyc){
        long double dist = norm(center - p.first) * p.second;
        if(dist <= mid + EPS){
          cnt++;
        }
      }
      max_cnt = max(max_cnt, cnt);
    }
    //cout << max_cnt << endl;
    if(max_cnt >= K){
      ur = mid;
    }else{
      lr = mid;
    }
  }
  cout << setprecision(20) << (lr + ur) / 2 << endl;
}

```