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>
using namespace std;
int n,k;
double x[66],y[66],ans=1e9+100,c[66];
queue<pair<pair<double,double>,double> >q;
vector<double>v;
double ddd(double xx,double yy,double aa)
{
	v.clear();
	for(int i=0;i<n;i++)
	{
		v.push_back(c[i]*sqrt(max(abs(x[i]-xx)-aa,0.0)*max(abs(x[i]-xx)-aa,0.0)+max(abs(y[i]-yy)-aa,0.0)*max(abs(y[i]-yy)-aa,0.0)));
	}
	sort(v.begin(),v.end());
	return v[k-1];
}
double nd(double xx,double yy)
{
	v.clear();
	for(int i=0;i<n;i++)
	{
		v.push_back(c[i]*sqrt((x[i]-xx)*(x[i]-xx)+(y[i]-yy)*(y[i]-yy)));
	}
	sort(v.begin(),v.end());
	return v[k-1];
}
int main()
{
	cout<<setprecision(10);
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i]>>c[i];
	}
	q.push(make_pair(make_pair(0.0,0.0),1000.0));
	while(!q.empty())
	{
		double xx=q.front().first.first,yy=q.front().first.second,dd,t=q.front().second;
		dd=ddd(xx,yy,t);
		q.pop();
		if((ans-dd)<=0.0000001*max(1.0,dd))
		{
			continue;
		}
		ans=min(ans,nd(xx,yy));
		for(double i=-0.5;i<=0.5;i+=1.0)
		{
			for(double j=-0.5;j<=0.5;j+=1.0)
			{
				q.push(make_pair(make_pair(xx+i*t,yy+j*t),t/2.0));
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}