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

Solution (in CPP):

Solution:
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

const ld eps = 1e-12;

int n, k;
vector<ld> x, y, c;
void input() {
	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];
}

// (px, py)に熱源をセットしたときの所要時間
ld get_time(ld px, ld py) {
	vector<ld> t(n);
	for (int i = 0; i < n; ++i) {
		ld dx = abs(px - x[i]);
		ld dy = abs(py - y[i]);
		ld d = sqrtl(dx * dx + dy * dy);
		t[i] = d * c[i];
	}
	sort(t.begin(), t.end());
	return t[k - 1];
}

// 二円の共有点
tuple<ld, ld, ld, ld> cross_circle(
	ld x1, ld y1, ld r1, ld x2, ld y2, ld r2
) {
	ld dx = abs(x1 - x2);
	ld dy = abs(y1 - y2);
	ld d_center = sqrtl(dx * dx + dy * dy);
	if (d_center < eps)
		return make_tuple(0.0L, 0.0L, 0.0L, 0.0L);
	if (d_center > r1 + r2 + eps)
		return make_tuple(0.0L, 0.0L, 0.0L, 0.0L);
	if (d_center + min(r1, r2) + eps < max(r1, r2))
		return make_tuple(0.0L, 0.0L, 0.0L, 0.0L);
	ld vec_x = y1 - y2, vec_y = x2 - x1;
	ld len = sqrtl(vec_x * vec_x + vec_y * vec_y);
	vec_x /= len, vec_y /= len;
	ld k = (r1 * r1 - r2 * r2 + d_center * d_center) / (2 * d_center);
	ld t = sqrtl(r1 * r1 - k * k);
	ld res_x1 = x1 + k * (x2 - x1) / d_center + t * vec_x;
	ld res_y1 = y1 + k * (y2 - y1) / d_center + t * vec_y;
	ld res_x2 = x1 + k * (x2 - x1) / d_center - t * vec_x;
	ld res_y2 = y1 + k * (y2 - y1) / d_center - t * vec_y;
	return make_tuple(res_x1, res_y1, res_x2, res_y2);
}

// t秒以内で条件を満たせるか
bool judge(ld t) {
	for (int i = 0; i < n; ++i)
		if (get_time(x[i], y[i]) < t + eps)
			return true;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			ld r1 = t / c[i], r2 = t / c[j];
			auto tmp = cross_circle(x[i], y[i], r1, x[j], y[j], r2);
			ld tmpx = get<0>(tmp), tmpy = get<1>(tmp);
			if (get_time(tmpx, tmpy) < t + eps) return true;
			tmpx = get<2>(tmp), tmpy = get<3>(tmp);
			if (get_time(tmpx, tmpy) < t + eps) return true;
		}
	}
	return false;
}

int main() {
	input();
	cout << setprecision(15);
	if (n == 1) {
		cout << 0 << endl;
	}
	else {
		ld ng = 0.0L, ok = 1000000.0L;
		while (ok - ng > eps) {
			ld mid = (ng + ok) / 2;
			if (judge(mid)) ok = mid;
			else ng = mid;
		}
		cout << ok << endl;
	}
	return 0;
}