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;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define fi first
#define se second
#define endl "\n"
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=61; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)==-1)exit(0); return x;} typedef pair<int,int> pii;
const int mod=(999983); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;}
//#define int ll
struct vec{
	lf x,y;
	explicit vec(lf x=0,lf y=0):x(x),y(y){}
	vec operator-(const vec &b){return vec(x-b.x,y-b.y);}
	vec operator+(const vec &b){return vec(x+b.x,y+b.y);}
	vec operator*(lf k){return vec(k*x,k*y);}
	lf len(){return hypot(x,y);}
	lf sqr(){return x*x+y*y;}
	vec trunc(lf k=1){return *this*(k/len());}
	vec rotate(double th){lf c=cos(th),s=sin(th); return vec(x*c-y*s,x*s+y*c);}
}a[N];
ostream &operator<<(ostream &o,const vec &v){return o<<'('<<v.x<<','<<v.y<<')';}
int n,k; lf c[N],s[N];

lf E(vec v){
	repeat(i,0,n)s[i]=(a[i]-v).len()*c[i];
	nth_element(s,s+k,s+n);
	return s[k];
}

lf rndf(){return rnd()*1.0/rnd.max();}
vec rndvec(){return vec(rndf()*2-1,rndf()*2-1);}
struct state{
	vec v; lf e;
	state(vec v=vec()):v(v),e(E(v)){}
	operator lf(){
		return e;
	}
};
state solve(){
	state X; lf T=1000;
	auto work=[&](){
		state Y=X.v+rndvec()*T;
		if(Y<X){X=Y; return 1;}
		return 0;
	};
	while(T>1e-9){
		if(work()){
			work(); work();
			T*=1.1;
		}
		T*=0.99992;
	}
	return X;
}

void Solve(){
	n=read(),k=read()-1;
	repeat(i,0,n)a[i].x=read(),a[i].y=read(),c[i]=read();
	state X=solve();
	repeat(i,0,5){
		state Y=solve();
		if(X>Y)X=Y;
	}
	printf("%.10f\n",lf(X));
}
signed main(){
	int T=1; //T=read();
	while(T--)Solve();
	return 0;
}