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:
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

double EPS = 1e-10;

int N, K;
int x[100], y[100], c[100];

int cntC(double x1, double y1, double T){
	int ret = 0;
	for(int i = 0; i < N; i++){
		double dx = x[i] - x1;
		double dy = y[i] - y1;
		// cout << dx * dx + dy * dy << " " << T * T / c[i] / c[i] << endl;
		if(dx * dx + dy * dy <= T * T / (c[i] * c[i]) * (1 + EPS)){
			ret += 1;
		}
	}
	// cout << ret << endl;
	return ret;
}

bool check(double T){
	// cout << "hoge" << endl;
	for(int i = 0; i < N; i++){
		for(int j = i + 1; j < N; j++){
			int dx = x[j] - x[i];
			int dy = y[j] - y[i];
			int d2 = dx * dx + dy * dy;
			double c1 = (double)c[i];
			double c2 = (double)c[j];
			double r12 = T * T / c1 / c1;
			double r22 = T * T / c2 / c2;
			double a = (d2 + r12 - r22) / 2;
			// cout << a << endl;
			// cout << dx << " " << dy << endl;
			if(d2 * r12 - a * a < 0){
				continue;
			}
			double sq = sqrt(d2 * r12 - a * a);
			// cout << (a * dx + dy * sq) / d2 + x[i] << " " << (a * dy - dx * sq) / d2 - y[i] << " " << cntC((a * dx + dy * sq) / d2 + x[i], (a * dy - dx * sq) / d2 - y[i], T) << endl;
			if(cntC((a * dx + dy * sq) / d2 + x[i], (a * dy - dx * sq) / d2 + y[i], T) >= K){
				return true;
			}
			// cout << (a * dx - dy * sq) / d2 - x[i] << " " << (a * dy + dx * sq) / d2 + y[i] << " " << cntC((a * dx - dy * sq) / d2 - x[i], (a * dy + dx * sq) / d2 + y[i], T) << endl;
			if(cntC((a * dx - dy * sq) / d2 - x[i], (a * dy + dx * sq) / d2 + y[i], T) >= K){
				return true;
			}
		}
		if(cntC(x[i], y[i], T) >= K){
			return true;
		}
	}
	return false;
}

int main(){
	cin >> N >> K;
	for(int i = 0; i < N; i++){
		cin >> x[i] >> y[i] >> c[i];
	}
	double L = 0, R = INF;
	while(R - L >= EPS){
		bool ret = check((L + R) / 2);
		if(ret){
			R = (L + R) / 2;
		}else{
			L = (L + R) / 2;
		}
	}
	printf("%.10f\n", R);
	return 0;
}