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 <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>

using namespace std;
typedef long long ll;

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

const double ep = 0.00000001;

bool IsEnoughTime(double t){
	for(int i = 0; i < N; i++){
		for(int j = i; j < N; j++){
			double xd = x[j]-x[i];
			double yd = y[j]-y[i];
			double r1 = t/c[i];
			double r2 = t/c[j];
			
			if(i == j){
				int count1 = 0;
				double X1 = x[i];
				double Y1 = y[i];
				
				for(int k = 0; k < N; k++){
					double rk = t / c[k];

					if((X1-x[k])*(X1-x[k]) + (Y1-y[k])*(Y1-y[k]) < rk*rk + ep){
						count1++;
					}
				}
				if(count1 >= K){
					return true;
				}
			}
			else if(xd*xd+yd*yd <= ((r1+r2)*(r1+r2)) && xd*xd+yd*yd >= (r1-r2)*(r1-r2)){
				//円i, 円j の交点を求める
				double a = (xd*xd + yd*yd + r1*r1-r2*r2)/2;
				double X1 = x[i] + (a*xd + yd * sqrt((xd*xd+yd*yd)*r1*r1-a*a))/(xd*xd+yd*yd);
				double Y1 = y[i] + (a*yd - xd * sqrt((xd*xd+yd*yd)*r1*r1-a*a))/(xd*xd+yd*yd);
				double X2 = x[i] + (a*xd - yd * sqrt((xd*xd+yd*yd)*r1*r1-a*a))/(xd*xd+yd*yd);
				double Y2 = y[i] + (a*yd + xd * sqrt((xd*xd+yd*yd)*r1*r1-a*a))/(xd*xd+yd*yd);
				
				int count1 = 0;
				int count2 = 0;
				for(int k = 0; k < N; k++){
					double rk = t / c[k];
					if((X1-x[k])*(X1-x[k]) + (Y1-y[k])*(Y1-y[k]) < rk*rk + ep){
						count1++;
					}
					if((X2-x[k])*(X2-x[k]) + (Y2-y[k])*(Y2-y[k]) < rk*rk + ep){
						count2++;
					}
				}
				if(count1 >= K || count2 >= K){
					return true;
				}
			}
		}
	}
	
	return false;
}

int main()
{
	scanf("%d %d", &N, &K);
	for(int i = 0; i < N; i++){
		scanf("%d %d %d", &x[i], &y[i], &c[i]);
	}
	
	double min = 0;
	double max = 2000*2000*100*100;
	
	while(max-min > ep){
		// printf("min %f max %f\n", min, max);
		double mid = min + (max-min)/2;
		if(IsEnoughTime(mid)){
			max = mid;
		}
		else{
			min = mid;
		}
	}
	
	printf("%.8f\n", min);
	
	return 0;
}