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:
#include <iostream>
#include <vector>
#include <complex>
#include <cstdio>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef complex<double> Point;

//円と円の交点. 接する場合も空のvectorを返す.
vector<Point> kouten_CC(Point c1, double r1, Point c2, double r2) {
	Point r = c2 - c1;
	if (norm(r) >= (r1 + r2) * (r1 + r2)) { return vector<Point>(); }
	if (min(r1, r2) + abs(r) <= max(r1, r2)) { return vector<Point>(); }
	double theta = acos((norm(r) + r1 * r1 - r2 * r2) / (2 * r1 * abs(r)));
	Point R = (r1 / abs(r)) * r;
	Point res1 = R * exp(Point(0, 1) * theta);
	Point res2 = R * exp(Point(0, 1) * (-theta));
	vector<Point> ret;
	ret.push_back(c1 + res1);
	ret.push_back(c1 + res2);
	return ret;
}

int n, K;
double x[60], y[60], c[60];

//答えがA以下か？
bool check(double A) {
	double r[60];
	int i, j, k;
	
	rep(i, n) r[i] = A / c[i];
	
	vector<Point> ps;
	rep(i, n) {
		ps.push_back(Point(x[i], y[i]));
		for (j = i + 1; j < n; j++) {
			ps.push_back((Point(x[i], y[i]) + Point(x[j], y[j])) * (double)0.5);
			vector<Point> p = kouten_CC(Point(x[i], y[i]), r[i], Point(x[j], y[j]), r[j]);
			rep(k, p.size()) {
				ps.push_back(p[k]);
				//cout << p[k] << endl;
			}
			if (p.size() == 2) {
				ps.push_back((p[0] + p[1]) * (double)0.5);
			}
		}
	}
	
	//交点ps[i]がK個以上の円に含まれるか判定.
	//誤差が無い場合、円jが交点ps[i]をギリギリ含むことがある。
	//誤差が無い場合、解hを小さくすることで誤魔化すのは難しい。(交点しか見ないため）
	//そこで、円jを少しだけ大きくしておいて判定する。
	double EPS = 1e-11;
	rep(i, n) r[i] += EPS;
	rep(i, ps.size()) {
		int cnt = 0;
		rep(j, n) {
			Point diff = Point(x[j], y[j]) - ps[i];
			if (abs(diff) <= r[j]) cnt++;
		}
		if (cnt >= K) return true;
	}
	return false;
}

int main() {
	int i;
	
	cin >> n >> K;
	rep(i, n) {
		cin >> x[i] >> y[i] >> c[i];
	}
	
	double st = 0, ed = 1e+7, mid;
	for (i = 0; i < 100; i++) {
		mid = (st + ed) / 2;
		if (check(mid)) { ed = mid; }
		else { st = mid; }
	}
	printf("%.14f\n", ed);
	return 0;
}