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 <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 2000000000
#define InfLL 4000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;

ld sqrt_(ld d) {
	assert(d >= 0.0);
	ld l = 0.0, r = 1000000.0;
	rep(q, 40) {
		ld m = (l + r) / 2.0;
		if (m * m >= d)
			r = m;
		else
			l = m;
	}
	return l;
}

int main() {
	int N, K;
	vd x, y, c;
	cin >> N >> K;
	x.resize(N);
	y.resize(N);
	c.resize(N);
	rep(i, N)
		cin >> x[i] >> y[i] >> c[i];
	ld L = 0.0, R = 1000000.0;
	rep(q, 40) {
		ld t = (L + R) / 2.0;
		//db tt = t;
		//printf("%.12f\n", tt);

		bool can = false;
		rep(i, N) {
			rep(j, N) {
				vector<ld> X(2), Y(2);
				if (i == j) {
					// 円の中心
					X[0] = x[i];
					Y[0] = y[i];
					X[1] = x[i];
					Y[1] = y[i];
				}
				else if (i > j) {
					// 円の交点
					ld A = (t / c[i]) * (t / c[i]);
					ld B = (t / c[j]) * (t / c[j]);
					ld C = (x[i] * x[i] - x[j] * x[j]) + (y[i] * y[i] - y[j] * y[j]) - (A - B);
					ld D = 2.0 * (x[i] - x[j]);
					ld E = 2.0 * (y[i] - y[j]);
					if (D == 0.0) {
						Y[0] = C / E;
						Y[1] = C / E;
						ld AY = A - (Y[0] - y[i]) * (Y[0] - y[i]);
						if (AY < 0.0)
							continue;
						X[0] = sqrt_(AY) + x[i];
						X[1] = -sqrt_(AY) + x[i];
					}
					else {
						ld F = C / D;
						ld G = E / D;
						ld H = F - x[i];
						ld a_ = G * G + 1;
						ld b_ = -1.0 * (G * H + y[i]);
						ld c_ = H * H + y[i] * y[i] - A;
						if (b_ * b_ - a_ * c_ < 0.0)
							continue;
						Y[0] = (-b_ + sqrt_(b_ * b_ - a_ * c_)) / a_;
						Y[1] = (-b_ + -sqrt_(b_ * b_ - a_ * c_)) / a_;
						X[0] = F - G * Y[0];
						X[1] = F - G * Y[1];
					}
				}
				else continue;

				rep(p, 2) {
					int k = 0;
					rep(n, N) {
						ld dist2 = (X[p] - x[n]) * (X[p] - x[n]) + (Y[p] - y[n]) * (Y[p] - y[n]);
						ld ttmp2 = c[n] * c[n] * dist2;
						if (ttmp2 <= t * t + 0.0000000001)
							k++;
					}
					if (k >= K)
						can = true;
				}
			}
		}
		if (can)
			R = t;
		else
			L = t;
	}
	db ans = L;
	printf("%.12f\n", ans);
	return 0;
}