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 "bits/stdc++.h"
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const double eps = 1e-9;
bool equal(double a, double b) { return abs(a - b) < eps; }

struct V {
	double x, y;
	V(double x = 0, double y = 0) : x(x), y(y) {}
	V operator+(const V& p) const { return V(x + p.x, y + p.y); }
	V operator-(const V& p) const { return V(x - p.x, y - p.y); }
	V operator*(double a) const { return V(x*a, y*a); }
	double sqrNorm() const { return x * x + y * y; }
	double norm() const { return sqrt(sqrNorm()); }
	V rotate90() const { return V(y, -x); }
};

struct Circle {
	V o; double r;
	Circle(V o = V(), double r = 0) : o(o), r(r) {}
	vector<V> xp(const Circle& c) {
		V v = c.o - o;
		double l = v.norm();
		if (equal(l, 0)) return {};
		if (equal(l + r + c.r, max({ l,r,c.r }) * 2)) {
			return { o + v * (r / l) };
		}
		if (l + r + c.r < max({ l,r,c.r }) * 2) return {};
		double x = -(c.r*c.r - l * l - r * r) / (2 * l);
		double y = sqrt(r*r - x * x);
		V mid = o + v * (x / l);
		v = v.rotate90();
		return { mid + v * (y / l), mid - v * (y / l) };
	}
	bool isInside(const V& p) {
		return (p - o).norm() < r + eps;
	}
};

int main() {
	int N,K;
	cin >> N>> K;
	if (K == 1) {
		cout << 0 << endl;
		return 0;
	}
	vector<Circle> c(N);
	for (int i = 0; i < N;++i) {
		cin >> c[i].o.x >> c[i].o.y >> c[i].r;
	}
	double l = 0, r = 400000;
	for (int ti = 0;ti<100;++ti) {
		double x = (l + r) / 2;
		vector<V>ps;
		//候補点を入れる
		for (int i = 0;i < N;++i) {
			ps.push_back(c[i].o);
		}
		for (int i = 0;i<N;++i) {
			for (int j = 0;j<i;++j) {
				Circle a = c[i], b = c[j];
				a.r = x / a.r;
				b.r = x / b.r;
				auto tmp = a.xp(b); 
				ps.insert(ps.end(), tmp.begin(), tmp.end());
			}
		}
		bool ok = false;
		for (V p : ps) {
			int cnt = 0;
			for (int ci = 0; ci < N;++ci) {
				Circle nc = c[ci];
				nc.r = x / nc.r;
				if (nc.isInside(p)) cnt++;
			}
			if (cnt >= K) ok = true;
		}
		if (ok) r = x; else l = x;
	}
	printf("%.10f\n", r);
	return 0;
}