#include "bits/stdc++.h"
using namespace std;

#define long

long double eps = 0.00000001;

int N, K;
vector<long double> X, Y, C;

pair<pair<long double, long double>, pair<long double, long double> > CLI(long double A, long double B, long double C, long double X1, long double Y1, long double R) {
	long double L = A * A + B * B;
	long double K = A * X1 + B * Y1 + C;
	long double D = L * R * R - K * K;
	long double Ds = sqrt(D);
	long double ApL = A / L;
	long double BpL = B / L;
	long double XC = X1 - ApL * K;
	long double YC = Y1 - BpL * K;
	long double XD = BpL * Ds;
	long double YD = ApL * Ds;
	return { {XC - XD, YC + YD}, {XC + XD, YC - YD} };
}

pair<pair<long double, long double>, pair<long double, long double> > CCI(long double X1, long double Y1, long double R1, long double X2, long double Y2, long double R2) {
	long double A = X1 - X2;
	long double B = Y1 - Y2;
	return CLI(A, B, 0.5 * ((R1 - R2) * (R1 + R2) - A * (X1 + X2) - B * (Y1 + Y2)), X1, Y1, R1);
}

long double Dist(long double X1, long double Y1, long double X2, long double Y2) {
	return sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2));
}

bool check(long double T) {
	for (int i = 0; i < N; i++) {
		int COUNT = 0;
		for (int j = 0; j < N; j++) {
			if (Dist(X[i], Y[i], X[j], Y[j]) * C[j] <= T + eps) COUNT++;
		}
		if (COUNT >= K) return true;
	}
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (Dist(X[i], Y[i], X[j], Y[j]) > T / C[i] + T / C[j] + eps) continue;
			pair<pair<long double, long double>, pair<long double, long double> > Ps = CCI(X[i], Y[i], T / C[i], X[j], Y[j], T / C[j]);
			int COUNT = 0;
			for (int k = 0; k < N; k++) {
				if (Dist(Ps.first.first, Ps.first.second, X[k], Y[k]) * C[k] <= T + eps) COUNT++;
			}
			if (COUNT >= K) return true;
			COUNT = 0;
			for (int k = 0; k < N; k++) {
				if (Dist(Ps.second.first, Ps.second.second, X[k], Y[k]) * C[k] <= T + eps) COUNT++;
			}
			if (COUNT >= K) return true;
		}
	}
	return false;
}

int main() {
	cin >> N >> K;
	X.resize(N), Y.resize(N), C.resize(N);
	for (int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> C[i];
	if (K == 1) {
		cout << 0 << endl;
		return 0;
	}
	long double L = 0.0, R = 200000.0;
	for (int i = 0; i < 50; i++) {
		long double MID = (L + R) / 2;
		check(MID) ? R = MID : L = MID;
		if (L + eps > R) break;
	}
	printf("%.12lf\n", L);
}
### Prompt

Your task is to create 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 long

long double eps = 0.00000001;

int N, K;
vector<long double> X, Y, C;

pair<pair<long double, long double>, pair<long double, long double> > CLI(long double A, long double B, long double C, long double X1, long double Y1, long double R) {
	long double L = A * A + B * B;
	long double K = A * X1 + B * Y1 + C;
	long double D = L * R * R - K * K;
	long double Ds = sqrt(D);
	long double ApL = A / L;
	long double BpL = B / L;
	long double XC = X1 - ApL * K;
	long double YC = Y1 - BpL * K;
	long double XD = BpL * Ds;
	long double YD = ApL * Ds;
	return { {XC - XD, YC + YD}, {XC + XD, YC - YD} };
}

pair<pair<long double, long double>, pair<long double, long double> > CCI(long double X1, long double Y1, long double R1, long double X2, long double Y2, long double R2) {
	long double A = X1 - X2;
	long double B = Y1 - Y2;
	return CLI(A, B, 0.5 * ((R1 - R2) * (R1 + R2) - A * (X1 + X2) - B * (Y1 + Y2)), X1, Y1, R1);
}

long double Dist(long double X1, long double Y1, long double X2, long double Y2) {
	return sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2));
}

bool check(long double T) {
	for (int i = 0; i < N; i++) {
		int COUNT = 0;
		for (int j = 0; j < N; j++) {
			if (Dist(X[i], Y[i], X[j], Y[j]) * C[j] <= T + eps) COUNT++;
		}
		if (COUNT >= K) return true;
	}
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (Dist(X[i], Y[i], X[j], Y[j]) > T / C[i] + T / C[j] + eps) continue;
			pair<pair<long double, long double>, pair<long double, long double> > Ps = CCI(X[i], Y[i], T / C[i], X[j], Y[j], T / C[j]);
			int COUNT = 0;
			for (int k = 0; k < N; k++) {
				if (Dist(Ps.first.first, Ps.first.second, X[k], Y[k]) * C[k] <= T + eps) COUNT++;
			}
			if (COUNT >= K) return true;
			COUNT = 0;
			for (int k = 0; k < N; k++) {
				if (Dist(Ps.second.first, Ps.second.second, X[k], Y[k]) * C[k] <= T + eps) COUNT++;
			}
			if (COUNT >= K) return true;
		}
	}
	return false;
}

int main() {
	cin >> N >> K;
	X.resize(N), Y.resize(N), C.resize(N);
	for (int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> C[i];
	if (K == 1) {
		cout << 0 << endl;
		return 0;
	}
	long double L = 0.0, R = 200000.0;
	for (int i = 0; i < 50; i++) {
		long double MID = (L + R) / 2;
		check(MID) ? R = MID : L = MID;
		if (L + eps > R) break;
	}
	printf("%.12lf\n", L);
}
```