#include <bits/stdc++.h>

using namespace std;

typedef long double cod;
using ld = cod;
double eps = 1e-7;
bool eq(cod a, cod b){ return abs(a - b) <= eps; }

struct vec{
	cod x, y; int id;
	vec(cod a = 0, cod b = 0) : x(a), y(b) {}
	vec operator+(const vec &o) const{
		return {x + o.x, y + o.y};
	}
	vec operator-(const vec &o) const{
		return {x - o.x, y - o.y};
	}
	vec operator*(const ld r) const {
		return {x * r, y * r};
	}
	cod operator*(const vec &o) const{ // cos
		return x * o.x + y * o.y;
	}
	cod len() const{
		return sqrtl(x * x + y * y); // <
	}
	cod len2() const{
		return (x * x + y * y); // <
	}
};

ld EPS = 1e-6;
// intersection of line a * x + b * y + c = 0
// and circle centered at the origin with radius r
vector<vec> f(ld r, ld a, ld b, ld c) {
	vector<vec> ans;

	ld x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
	if(c*c > r*r*(a*a+b*b)+EPS) {

	}
	else if(abs(c*c - r*r*(a*a+b*b)) < EPS){
		ans.push_back(vec(x0, y0));
	}
	else {
		ld d = r*r - c*c/(a*a+b*b);
		ld mult = sqrt (d / (a*a+b*b));
		ld ax, ay, bx, by;
		ax = x0 + b * mult;
		bx = x0 - b * mult;
		ay = y0 - a * mult;
		by = y0 + a * mult;
		ans.push_back(vec(ax, ay));
		ans.push_back(vec(bx, by));
	}
	return ans;
}

struct circle {
	vec c; cod r;
	circle() : c(0, 0), r(0) {}
	circle(const vec o, cod val = 0) : c(o), r(val) {}
	bool inside(const vec &a) const {
		return (a - c).len2() <= r * r + EPS;
	}
	vector<vec> inter(const circle &o) const {
		ld d2 = (c - o.c).len2();
		if(d2 > (r + o.r) * (r + o.r) + EPS) return vector<vec>();
		if(d2 + EPS < (r - o.r) * (r - o.r)) return vector<vec>();

		auto c2 = o.c - c;

		auto ans = f(r, -2 * c2.x, -2 * c2.y, (c2 * c2) + r * r - o.r * o.r);
		for(vec &p : ans) p = p + c;
		return ans;
	}
};

const int N = 66;
int n, k;
int x[N], y[N], c[N];

circle h[N];

int f(ld t) {
	for(int i = 0; i < n; i++) {
		h[i] = circle(vec(x[i], y[i]), t / c[i]);
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			for(vec p : h[i].inter(h[j])) {
				int tmp = 0;
				for(int w = 0; w < n; w++) {
					tmp += h[w].inside(p);
				}
				ans = max(ans, tmp);
			}
		}
	}
	for(int i = 0; i < n; i++) {
		int tmp = 0;
		for(int j = 0; j < n; j++) {
			tmp += h[j].inside(h[i].c);
		}
		ans = max(ans, tmp);
	}
	return ans;
}

int main() {

	/*auto aa = circle(vec(1, 0), 2);
	auto bb = circle(vec(3, 0), 2);

	for(vec p : aa.inter(bb)) {
		cout << p.x << " " << p.y << endl;
	}*/

	scanf("%d %d", &n, &k);
	if(k == 1) return printf("0\n"), 0;

	for(int i = 0; i < n; i++) scanf("%d %d %d", x + i, y + i, c + i);

	ld lo = 0, hi = 1e9;

	for(int it = 0; it < 200; it++) {
		auto mid = (lo + hi) / 2;
		// int val = f(mid);
		// printf("%Lf -> %d\n", mid, val);
		if(f(mid) >= k) hi = mid;
		else lo = mid;
	}
	printf("%.20Lf\n", lo);

}

### Prompt

Develop a solution in CPP 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 <bits/stdc++.h>

using namespace std;

typedef long double cod;
using ld = cod;
double eps = 1e-7;
bool eq(cod a, cod b){ return abs(a - b) <= eps; }

struct vec{
	cod x, y; int id;
	vec(cod a = 0, cod b = 0) : x(a), y(b) {}
	vec operator+(const vec &o) const{
		return {x + o.x, y + o.y};
	}
	vec operator-(const vec &o) const{
		return {x - o.x, y - o.y};
	}
	vec operator*(const ld r) const {
		return {x * r, y * r};
	}
	cod operator*(const vec &o) const{ // cos
		return x * o.x + y * o.y;
	}
	cod len() const{
		return sqrtl(x * x + y * y); // <
	}
	cod len2() const{
		return (x * x + y * y); // <
	}
};

ld EPS = 1e-6;
// intersection of line a * x + b * y + c = 0
// and circle centered at the origin with radius r
vector<vec> f(ld r, ld a, ld b, ld c) {
	vector<vec> ans;

	ld x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
	if(c*c > r*r*(a*a+b*b)+EPS) {

	}
	else if(abs(c*c - r*r*(a*a+b*b)) < EPS){
		ans.push_back(vec(x0, y0));
	}
	else {
		ld d = r*r - c*c/(a*a+b*b);
		ld mult = sqrt (d / (a*a+b*b));
		ld ax, ay, bx, by;
		ax = x0 + b * mult;
		bx = x0 - b * mult;
		ay = y0 - a * mult;
		by = y0 + a * mult;
		ans.push_back(vec(ax, ay));
		ans.push_back(vec(bx, by));
	}
	return ans;
}

struct circle {
	vec c; cod r;
	circle() : c(0, 0), r(0) {}
	circle(const vec o, cod val = 0) : c(o), r(val) {}
	bool inside(const vec &a) const {
		return (a - c).len2() <= r * r + EPS;
	}
	vector<vec> inter(const circle &o) const {
		ld d2 = (c - o.c).len2();
		if(d2 > (r + o.r) * (r + o.r) + EPS) return vector<vec>();
		if(d2 + EPS < (r - o.r) * (r - o.r)) return vector<vec>();

		auto c2 = o.c - c;

		auto ans = f(r, -2 * c2.x, -2 * c2.y, (c2 * c2) + r * r - o.r * o.r);
		for(vec &p : ans) p = p + c;
		return ans;
	}
};

const int N = 66;
int n, k;
int x[N], y[N], c[N];

circle h[N];

int f(ld t) {
	for(int i = 0; i < n; i++) {
		h[i] = circle(vec(x[i], y[i]), t / c[i]);
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			for(vec p : h[i].inter(h[j])) {
				int tmp = 0;
				for(int w = 0; w < n; w++) {
					tmp += h[w].inside(p);
				}
				ans = max(ans, tmp);
			}
		}
	}
	for(int i = 0; i < n; i++) {
		int tmp = 0;
		for(int j = 0; j < n; j++) {
			tmp += h[j].inside(h[i].c);
		}
		ans = max(ans, tmp);
	}
	return ans;
}

int main() {

	/*auto aa = circle(vec(1, 0), 2);
	auto bb = circle(vec(3, 0), 2);

	for(vec p : aa.inter(bb)) {
		cout << p.x << " " << p.y << endl;
	}*/

	scanf("%d %d", &n, &k);
	if(k == 1) return printf("0\n"), 0;

	for(int i = 0; i < n; i++) scanf("%d %d %d", x + i, y + i, c + i);

	ld lo = 0, hi = 1e9;

	for(int it = 0; it < 200; it++) {
		auto mid = (lo + hi) / 2;
		// int val = f(mid);
		// printf("%Lf -> %d\n", mid, val);
		if(f(mid) >= k) hi = mid;
		else lo = mid;
	}
	printf("%.20Lf\n", lo);

}

```