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 <algorithm>
#include <cmath>
#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repn(i, a, b) for(int i = (a); i < (b); ++i)

struct Point {
	double x, y;

	Point() = default;
	Point(double x_, double y_) : x(x_), y(y_) {}

	Point operator+(const Point& rhs) const { return Point(x + rhs.x, y + rhs.y); }
	Point operator-(const Point& rhs) const { return Point(x - rhs.x, y - rhs.y); }

	double length() const { return sqrt(x * x + y * y); }
	double distanceFrom(const Point& rhs) const { return (*this - rhs).length(); }

	friend istream& operator>>(istream& is, Point& rhs) { return is >> rhs.x >> rhs.y; }
};

struct Circle {
	Point p;
	double r;

	Circle() = default;
	Circle(const Point& p_, double r_) :p(p_), r(r_) {}

	bool contains(const Point& rhs) const {
		return p.distanceFrom(rhs) < r + 1e-8;
	}

	vector<Point> intersections(const Circle& rhs) const {
		double d = p.distanceFrom(rhs.p), r1 = rhs.r;
		if (d > r + r1 + 1e-8 || fabs(r - r1) > d + 1e-8) return vector<Point>();
		else {
			double theta = acos((d * d + r * r - r1 * r1) / (2 * d * r));
			double a = atan2(rhs.p.y - p.y, rhs.p.x - p.x);
			vector<Point> res;
			for (int i = -1; i <= 1; i += 2) {
				res.emplace_back(p + Point(r * cos(a + i * theta), r * sin(a + i * theta)));
			}
			return res;
		}
	}

	friend istream& operator>>(istream& is, Circle& cir) { return is >> cir.p >> cir.r; }
};

int n, k;
Circle cir[60];
double rad[60];

int g(const Point& p) {
	int res = 0;
	rep(i, n) {
		if (cir[i].contains(p)) ++res;
	}
	return res;
}

bool f() {
	rep(i, n) {
		if (k <= g(cir[i].p)) return true;
	}

	rep(i, n - 1) {
		const Circle& c = cir[i];
		repn(j, i + 1, n) {
			for (const Point& c1 : c.intersections(cir[j])) {
				if (k <= g(c1)) return true;
			}
		}
	}
	return false;
}

void update(double t) {
	rep(i, n) {
		cir[i].r = t / rad[i];
	}
}

int main() {
	cin >> n >> k;
	rep(i, n) {
		cin >> cir[i];
		rad[i] = cir[i].r;
	}
	double l = 0.0, r = 5.0 * 1e5, eps = 1e-7;
	while (fabs(r - l) > eps) {
		double mid = 0.5 * (l + r);
		update(mid);
		if (f()) r = mid;
		else l = mid;
	}
	printf("%.7lf\n",r);
}