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<bits/stdc++.h>
#include<queue>
using namespace std;
struct node{
	double x,y,c;
}a[100];
int n,k;
double f(double l,double r)
{
	if(l+0.0000000001>r)
	{
		return (l+r)/2;
	}
	double m=(l+r)/2;
	queue<pair<double,double> > que;
	for(int i=0;i<n;i++)
	{
		que.push(make_pair(a[i].x,a[i].y));
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			double x1=a[i].x,y1=a[i].y,r1=m/a[i].c;
			double x2=a[j].x,y2=a[j].y,r2=m/a[j].c;
			double dx=x2-x1,dy=y2-y1;
			double a=dx*dx+dy*dy;
			double b=((r1*r1-r2*r2)/a+1)/2;
			double d=r1*r1/a-b*b;
			if(d>=0)
			{
				d=sqrt(d);
				double x3=x1+dx*b;
				double y3=y1+dy*b;
				double x4=-dy*d;
				double y4=dx*d;
				que.push(make_pair(x3-x4,y3-y4));
				que.push(make_pair(x3+x4,y3+y4));
			}
		}
	}
	int nu=0;
//	printf("%lf \n",m);
	while(que.size()!=0)
	{
		pair<double,double> p=que.front();
//		printf("%lf %lf\n",p.first,p.second);
		que.pop();
		int nq=0;
		for(int i=0;i<n;i++)
		{
			double r=m/a[i].c;
			double dx=p.first-a[i].x;
			double dy=p.second-a[i].y;
			if(dy*dy+dx*dx-r*r<=0.0000001)
			{
				nq++;
			}
		}
		nu=max(nu,nq);
	}
	if(nu>=k)
	{
		return f(l,m);
	}
	else
	{
		return f(m,r);
	}
}
int main(void)
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].c);
	}
	if(k==1)
	{
		printf("0");
	}
	else
	{
		printf("%.10lf",f(0,1e6*1.0));
	}
}