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 <math.h>
#define maxn 65
#define eps 1e-8
double x[maxn],y[maxn],c[maxn],X[65*65*2],Y[65*65*2],r[maxn];
int tot,N,K;
double dis(double x,double y,double c,double X,double Y){
	return c*sqrt((X-x)*(X-x)+(Y-y)*(Y-y));
}
void cal(double x1,double y1,double r1,double x2,double y2,double r2){//计算两圆交点坐标
	double D;//A=a*a,H=h*h,D=d*d;
	double ad,h;//ad=a*d;
	D=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
	if(D==0)return;
	ad=(r1*r1+D-r2*r2)/2;//2*a*d=r1*r1+D-r2*r2
	h=D*r1*r1-ad*ad;
	if(h<0)return;//漏了此句的判定
	h=sqrt(h);
	tot++,X[tot]=x1+ad*(x2-x1)/D-(y2-y1)*h/D,Y[tot]=y1+ad*(y2-y1)/D+(x2-x1)*h/D;
	tot++,X[tot]=x1+ad*(x2-x1)/D+(y2-y1)*h/D,Y[tot]=y1+ad*(y2-y1)/D-(x2-x1)*h/D;
}
int judge(double t){
	int i,j,cnt;
	for(i=1;i<=N;i++)r[i]=t/c[i];
	tot=0;
	for(i=1;i<=N;i++){
		tot++,X[tot]=x[i],Y[tot]=y[i];//tot++,X[i]=x[i],Y[i]=y[i];
		for(j=i+1;j<=N;j++)
			cal(x[i],y[i],r[i],x[j],y[j],r[j]);
	}
	for(i=1;i<=tot;i++){
		cnt=0;
		for(j=1;j<=N;j++)
			if(dis(x[j],y[j],c[j],X[i],Y[i])<t+eps)cnt++;//浮点比大小无等于的情况，这是由浮点误差决定的。if(dis(x[j],y[j],c[j],X[i],Y[i])<t+eps)cnt++;
		if(cnt>=K)return 1;
	}
	return 0;
}
int main(){
	double l,r,mid;
	int i;
	scanf("%d%d",&N,&K);
	for(i=1;i<=N;i++)scanf("%lf%lf%lf",&x[i],&y[i],&c[i]);
	l=0,r=1000010;
	for(i=1;i<=100;i++){
		mid=(l+r)/2;
		if(judge(mid))r=mid;
		else l=mid;
	}
	printf("%.6lf\n",r);
	return 0;
}