#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>

using namespace std;

double getD(double x1, double y1, double x2, double y2) {
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

double getDS(double x1, double y1, double x2, double y2) {
	return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}

vector<double> getI(double x1, double y1, double r1, double x2, double y2, double r2) {
	double d = getD(x1, y1, x2, y2);
	double ds = getDS(x1, y1, x2, y2);
	double a = (r1*r1-r2*r2+ds)/(2.0*d);
	double h = sqrt(r1*r1-a*a);
	double x0 = x1 + (x2-x1)*a/d;
	double y0 = y1 + (y2-y1)*a/d;
	double xc = x0 - (y2-y1)*h/d;
	double yc = y0 + (x2-x1)*h/d;
	double xd = x0 + (y2-y1)*h/d;
	double yd = y0 - (x2-x1)*h/d;
	return {xc, yc, xd, yd};
}

bool check(const vector<vector<double>> &p, const vector<vector<double>> &c, const int k) {
	for (auto &i : p) {
		int res = 0;
		for (auto &j : c) {
			double d = getD(i[0], i[1], j[0], j[1]);
			if (d - j[2] < 1e-6) {
				res++;
				if (res == k) {
					return true;
				}
			}
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	int n, k;
	cin>>n>>k;
	if (k == 1) {
		cout<<0<<endl;
		return 0;
	}
	vector<vector<double>> v;
	for (int i = 0; i < n; i++) {
		double x, y, c;
		cin>>x>>y>>c;
		v.push_back({x, y, c});
	}
	double lo = 0, hi = 400000;
	while (abs(hi-lo) > 1e-6) {
		double t = (lo + hi) / 2.0;
		vector<vector<double>> c;
		vector<vector<double>> p;
		for (auto &i : v) {
			c.push_back({i[0], i[1], t/(double)i[2]});
			p.push_back({i[0], i[1]});
		}
		const int m = c.size();
		for (int i = 0; i < m-1; i++) {
			for (int j = i+1; j < m; j++) {
				double d = getD(c[i][0], c[i][1], c[j][0], c[j][1]);
				if (d >= abs(c[i][2] - c[j][2]) && d <= c[i][2] + c[j][2]) {
					auto s = getI(c[i][0], c[i][1], c[i][2], c[j][0], c[j][1], c[j][2]);
					p.push_back({s[0], s[1]});
					p.push_back({s[2], s[3]});
				}
			}
		}
		bool res = check(p, c, k);
		if (res) {
			hi = t;
		} else {
			lo = t;
		}
	}
	printf("%.6f\n", lo);
	return 0;
}
### Prompt

Generate a cpp solution 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 <vector>
#include <cmath>
#include <algorithm>
#include <utility>

using namespace std;

double getD(double x1, double y1, double x2, double y2) {
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

double getDS(double x1, double y1, double x2, double y2) {
	return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}

vector<double> getI(double x1, double y1, double r1, double x2, double y2, double r2) {
	double d = getD(x1, y1, x2, y2);
	double ds = getDS(x1, y1, x2, y2);
	double a = (r1*r1-r2*r2+ds)/(2.0*d);
	double h = sqrt(r1*r1-a*a);
	double x0 = x1 + (x2-x1)*a/d;
	double y0 = y1 + (y2-y1)*a/d;
	double xc = x0 - (y2-y1)*h/d;
	double yc = y0 + (x2-x1)*h/d;
	double xd = x0 + (y2-y1)*h/d;
	double yd = y0 - (x2-x1)*h/d;
	return {xc, yc, xd, yd};
}

bool check(const vector<vector<double>> &p, const vector<vector<double>> &c, const int k) {
	for (auto &i : p) {
		int res = 0;
		for (auto &j : c) {
			double d = getD(i[0], i[1], j[0], j[1]);
			if (d - j[2] < 1e-6) {
				res++;
				if (res == k) {
					return true;
				}
			}
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	int n, k;
	cin>>n>>k;
	if (k == 1) {
		cout<<0<<endl;
		return 0;
	}
	vector<vector<double>> v;
	for (int i = 0; i < n; i++) {
		double x, y, c;
		cin>>x>>y>>c;
		v.push_back({x, y, c});
	}
	double lo = 0, hi = 400000;
	while (abs(hi-lo) > 1e-6) {
		double t = (lo + hi) / 2.0;
		vector<vector<double>> c;
		vector<vector<double>> p;
		for (auto &i : v) {
			c.push_back({i[0], i[1], t/(double)i[2]});
			p.push_back({i[0], i[1]});
		}
		const int m = c.size();
		for (int i = 0; i < m-1; i++) {
			for (int j = i+1; j < m; j++) {
				double d = getD(c[i][0], c[i][1], c[j][0], c[j][1]);
				if (d >= abs(c[i][2] - c[j][2]) && d <= c[i][2] + c[j][2]) {
					auto s = getI(c[i][0], c[i][1], c[i][2], c[j][0], c[j][1], c[j][2]);
					p.push_back({s[0], s[1]});
					p.push_back({s[2], s[3]});
				}
			}
		}
		bool res = check(p, c, k);
		if (res) {
			hi = t;
		} else {
			lo = t;
		}
	}
	printf("%.6f\n", lo);
	return 0;
}
```