#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <ccomplex>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;


namespace geom {

using Float = double;
using Point = complex<Float>;
constexpr Float EPS = 1e-9;

inline int sgn(const Float &r) {
	return (r > EPS) - (r < -EPS);
}
bool operator==(const Point &a, const Point &b) {
	bool xeq = sgn(real(a) - real(b)) == 0;
	bool yeq = sgn(imag(a) - imag(b)) == 0;
	return xeq && yeq;
}
bool operator<(const Point &a, const Point &b) {
	Float xsgn = sgn(real(a) - real(b));
	if (xsgn == 0) {
		return sgn(imag(a) - imag(b)) < 0;
	}
	return xsgn < 0;
}

Float dot(const Point &a, const Point &b) {
	return real(conj(a)*b);
}
Float cross(const Point &a, const Point &b) {
	return imag(conj(a)*b);
}

struct Circle {
	Point center;
	Float radius;

	Circle() {}
	Circle(const Point &center, const Float &radius)
		: center(center), radius(radius) {}

	// 1: interior, 0: boundary, -1: exterior
	int relation(const Point &p) {
		return sgn(radius - abs(p - center));
	}
};

vector<Point> intersection(const Circle &a, const Circle &b) {
	Point p = b.center - a.center;
	Float d = norm(p);
	Float t = (d + a.radius*a.radius - b.radius*b.radius) / 2.;
	Float q = d*a.radius*a.radius - t*t;
	int qsgn = sgn(q);
	vector<Point> ret;
	if (qsgn < 0) return ret;
	ret.emplace_back(
		(t*real(p) + imag(p)*sqrt(q)) / d,
		(t*imag(p) - real(p)*sqrt(q)) / d
	);
	if (qsgn > 0) {
		ret.emplace_back(
			(t*real(p) - imag(p)*sqrt(q)) / d,
			(t*imag(p) + real(p)*sqrt(q)) / d
		);
	}
	for (auto &x : ret) {
		x += a.center;
	}
	return ret;
}

}

int main() {
	int n, k; cin >> n >> k;
	vector<geom::Circle> circ(n);
	for (int i = 0; i < n; i++) {
		geom::Float a, b, r;
		cin >> a >> b >> r;
		circ[i].center = { a, b };
		circ[i].radius = 1. / r;
	}

	auto cntp = [&](geom::Point p) {
		int cnt = 0;
		for (const auto &c : circ) {
			cnt += geom::sgn(abs(p - c.center) - c.radius) <= 0;
		}
		return cnt;
	};
	double lo = 0, hi = 1e9;
	for (int iter = 0; iter < 100; iter++) {
		double mid = (lo + hi) / 2;
		for (auto &c : circ) c.radius *= mid;
		bool flag = false;
		for (const auto &c : circ) {
			flag |= cntp(c.center) >= k;
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				auto v = move(geom::intersection(circ[i], circ[j]));
				for (const auto& p : v) {
					flag |= cntp(p) >= k;
				}
			}
		}
		if (flag) hi = mid;
		else lo = mid;
		for (auto &c : circ) c.radius /= mid;
	}
	printf("%.10f\n", lo);
	return 0;
}

### Prompt

Create a solution in CPP for 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 <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <ccomplex>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;


namespace geom {

using Float = double;
using Point = complex<Float>;
constexpr Float EPS = 1e-9;

inline int sgn(const Float &r) {
	return (r > EPS) - (r < -EPS);
}
bool operator==(const Point &a, const Point &b) {
	bool xeq = sgn(real(a) - real(b)) == 0;
	bool yeq = sgn(imag(a) - imag(b)) == 0;
	return xeq && yeq;
}
bool operator<(const Point &a, const Point &b) {
	Float xsgn = sgn(real(a) - real(b));
	if (xsgn == 0) {
		return sgn(imag(a) - imag(b)) < 0;
	}
	return xsgn < 0;
}

Float dot(const Point &a, const Point &b) {
	return real(conj(a)*b);
}
Float cross(const Point &a, const Point &b) {
	return imag(conj(a)*b);
}

struct Circle {
	Point center;
	Float radius;

	Circle() {}
	Circle(const Point &center, const Float &radius)
		: center(center), radius(radius) {}

	// 1: interior, 0: boundary, -1: exterior
	int relation(const Point &p) {
		return sgn(radius - abs(p - center));
	}
};

vector<Point> intersection(const Circle &a, const Circle &b) {
	Point p = b.center - a.center;
	Float d = norm(p);
	Float t = (d + a.radius*a.radius - b.radius*b.radius) / 2.;
	Float q = d*a.radius*a.radius - t*t;
	int qsgn = sgn(q);
	vector<Point> ret;
	if (qsgn < 0) return ret;
	ret.emplace_back(
		(t*real(p) + imag(p)*sqrt(q)) / d,
		(t*imag(p) - real(p)*sqrt(q)) / d
	);
	if (qsgn > 0) {
		ret.emplace_back(
			(t*real(p) - imag(p)*sqrt(q)) / d,
			(t*imag(p) + real(p)*sqrt(q)) / d
		);
	}
	for (auto &x : ret) {
		x += a.center;
	}
	return ret;
}

}

int main() {
	int n, k; cin >> n >> k;
	vector<geom::Circle> circ(n);
	for (int i = 0; i < n; i++) {
		geom::Float a, b, r;
		cin >> a >> b >> r;
		circ[i].center = { a, b };
		circ[i].radius = 1. / r;
	}

	auto cntp = [&](geom::Point p) {
		int cnt = 0;
		for (const auto &c : circ) {
			cnt += geom::sgn(abs(p - c.center) - c.radius) <= 0;
		}
		return cnt;
	};
	double lo = 0, hi = 1e9;
	for (int iter = 0; iter < 100; iter++) {
		double mid = (lo + hi) / 2;
		for (auto &c : circ) c.radius *= mid;
		bool flag = false;
		for (const auto &c : circ) {
			flag |= cntp(c.center) >= k;
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				auto v = move(geom::intersection(circ[i], circ[j]));
				for (const auto& p : v) {
					flag |= cntp(p) >= k;
				}
			}
		}
		if (flag) hi = mid;
		else lo = mid;
		for (auto &c : circ) c.radius /= mid;
	}
	printf("%.10f\n", lo);
	return 0;
}

```