#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;
const ll MOD = 1000000007;

using cplx = complex<double>;
const double pi = atan2(0, -1);

double dat[62][3];
pair<cplx, double> niku[62];

double dist(cplx x, cplx y) {
	double xd = x.real() - y.real();
	double yd = x.imag() - y.imag();
	return sqrt(xd * xd + yd * yd);
}

int main() {
	int N, K;
	double x, y, c;
	cin >> N >> K;
	cplx P;
	for (int i = 0;i < N;i++) {
		cin >> x >> y >> c;
		P = { x,y };
		niku[i] = { P,c };
	}

	double ok = 500000, ng = 0, mid;
	vector<pair<double, bool>> cross, SS;
	double dd, xr, nr, mr, otr;

	int din, mxi, amx;
	for (int zzz = 0;zzz < 80;zzz++) {
		mid = (ok + ng) / 2;
		amx = 0;
		for (int i = 0;i < N;i++) {
			din = 1;
			for (int j = 0;j < N;j++) {
				if (i == j)continue;
				dd = dist(niku[i].first, niku[j].first);
				mr = mid / niku[i].second;
				otr = mid / niku[j].second;
				xr = max(mr, otr);
				nr = min(mr, otr);

				if (dd <= mr + otr) {
					if (dd + mr < otr) {
						//内包関係
						din++;
					}
					else if (dd + otr < mr) {
						//自分が含んでしまっている内包
					} 
					else {
						//2点で交わる
						//cout << mr << " " << otr << " " << dd << endl;
						double ct = (mr * mr + dd * dd - otr * otr) / (2 * mr * dd);
						//cout << ct << endl;
						double ag = acos(ct);
						//cout << i << " " << j << " " << ag << endl;
						double ags = arg(niku[j].first - niku[i].first) - ag;
						double agb = arg(niku[j].first - niku[i].first) + ag;
						if (ags < 0 && agb > 0)din++;


						cross.push_back({ ags,0 });
						cross.push_back({ agb,1 });
						cross.push_back({ ags + 2 * pi,0 });
						cross.push_back({ agb + 2 * pi,1 });
						cross.push_back({ ags + 4 * pi,0 });
						cross.push_back({ agb + 4 * pi,1 });
					}
				}
			}

			sort(all(cross));

			mxi = din;
			for (auto th : cross) {
				if (th.first < 0)continue;
				if (th.first > 2 * pi)break;
				if (th.second) {
					din--;
				}
				else {
					din++;
				}
				mxi = max(din, mxi);
			}
			amx = max(amx, mxi);
			cross = SS;
		}

		if (amx < K)ng = mid;
		else ok = mid;
	}
	printf("%.10f\n", ok);
}
### Prompt

Your challenge is to write 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 <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;
const ll MOD = 1000000007;

using cplx = complex<double>;
const double pi = atan2(0, -1);

double dat[62][3];
pair<cplx, double> niku[62];

double dist(cplx x, cplx y) {
	double xd = x.real() - y.real();
	double yd = x.imag() - y.imag();
	return sqrt(xd * xd + yd * yd);
}

int main() {
	int N, K;
	double x, y, c;
	cin >> N >> K;
	cplx P;
	for (int i = 0;i < N;i++) {
		cin >> x >> y >> c;
		P = { x,y };
		niku[i] = { P,c };
	}

	double ok = 500000, ng = 0, mid;
	vector<pair<double, bool>> cross, SS;
	double dd, xr, nr, mr, otr;

	int din, mxi, amx;
	for (int zzz = 0;zzz < 80;zzz++) {
		mid = (ok + ng) / 2;
		amx = 0;
		for (int i = 0;i < N;i++) {
			din = 1;
			for (int j = 0;j < N;j++) {
				if (i == j)continue;
				dd = dist(niku[i].first, niku[j].first);
				mr = mid / niku[i].second;
				otr = mid / niku[j].second;
				xr = max(mr, otr);
				nr = min(mr, otr);

				if (dd <= mr + otr) {
					if (dd + mr < otr) {
						//内包関係
						din++;
					}
					else if (dd + otr < mr) {
						//自分が含んでしまっている内包
					} 
					else {
						//2点で交わる
						//cout << mr << " " << otr << " " << dd << endl;
						double ct = (mr * mr + dd * dd - otr * otr) / (2 * mr * dd);
						//cout << ct << endl;
						double ag = acos(ct);
						//cout << i << " " << j << " " << ag << endl;
						double ags = arg(niku[j].first - niku[i].first) - ag;
						double agb = arg(niku[j].first - niku[i].first) + ag;
						if (ags < 0 && agb > 0)din++;


						cross.push_back({ ags,0 });
						cross.push_back({ agb,1 });
						cross.push_back({ ags + 2 * pi,0 });
						cross.push_back({ agb + 2 * pi,1 });
						cross.push_back({ ags + 4 * pi,0 });
						cross.push_back({ agb + 4 * pi,1 });
					}
				}
			}

			sort(all(cross));

			mxi = din;
			for (auto th : cross) {
				if (th.first < 0)continue;
				if (th.first > 2 * pi)break;
				if (th.second) {
					din--;
				}
				else {
					din++;
				}
				mxi = max(din, mxi);
			}
			amx = max(amx, mxi);
			cross = SS;
		}

		if (amx < K)ng = mid;
		else ok = mid;
	}
	printf("%.10f\n", ok);
}
```