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>
#define STDIO
#define MOD 1000000007
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
#define lowbit(x) ((x)&(-x))
#define INF MOD
#define EPS (5e-7)
using namespace std;
int n,k;
typedef pair<pair<double,double>,double> ttt;
#define x_pos first.first
#define y_pos first.second
#define activity second
queue<ttt> q;
double x[62],y[62],c[62];
double xp,yp,ap,nx,ny,na;
double optimistic(double xx,double yy,double aa){
	//乐观估价函数
	vector<double> aux;
	for(int i=1;i<=n;i++)
		aux.push_back(c[i]*hypot(max(abs(x[i]-xx)-aa,0.000),max(abs(y[i]-yy)-aa,0.000)));
	nth_element(aux.begin(),aux.begin()+k-1,aux.end());
	return aux[k-1];
}
double realistic(double xx,double yy){
	//真实情况函数
	vector<double> aux;
	for(int i=1;i<=n;i++)
		aux.push_back(c[i]*hypot(x[i]-xx,y[i]-yy));
	nth_element(aux.begin(),aux.begin()+k-1,aux.end());
	return aux[k-1];
}
int main(){
	#ifndef STDIO
		freopen("input.in","r",stdin);
		freopen("output.out","w",stdout);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i]>>c[i];
	q.push(make_pair(make_pair(0,0),1000));
	double res=1e9;
	cout<<fixed<<setprecision(15);
	double opti;
	while(q.size()){
		xp=q.front().x_pos;
		yp=q.front().y_pos;
		ap=q.front().activity;
		q.pop();
		//x坐标：xp
		//y坐标:yp
		//活动半径:ap
		opti=optimistic(xp,yp,ap);
		if(res-opti<=5e-7*max(1.0,opti))//乐观函数 
			continue;
		res=min(res,realistic(xp,yp));//现实情况 
		for(double mx:{-0.5,0.5}){
			for(double my:{-0.5,0.5}){
				q.push(make_pair(make_pair(xp+mx*ap,yp+my*ap),ap/2));
			}
		}
	}
	cout<<res<<endl;
	return 0;
}