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;

typedef long long ll;
typedef unsigned long long ull;
typedef double D;
typedef complex<D> P;
#define X real()
#define Y imag()
const D eps=1e-8;
const D inf=1e12;
const D PI=acos(-1);

#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

struct C{
  P p; D r;
  C(const P& p,D r):p(p),r(r){}
};

enum RELATION{SAME=1,CONTAINED=2,OVER=4,NO_CROSS=8,ONE_CROSS=16,ONE_CONTAINED_CROSS=32,ONE_OVER_CROSS=64,TWO_CROSS=128};
int cRel(C c1, C c2) {
  D d=abs(c1.p-c2.p);
  D dr1=c1.r-c2.r,dr2=c2.r-c1.r;
  D ar=c1.r+c2.r;
  if(d<eps&&c1.r==c2.r)return SAME;
  if(d<dr1)return OVER;
  if(d<dr2)return CONTAINED;
  if(d==dr1)return ONE_OVER_CROSS;
  if(d==dr2)return ONE_CONTAINED_CROSS;
  if(d==ar)return ONE_CROSS;
  if(d>ar)return NO_CROSS;
  return TWO_CROSS;
}

void crosspointCC(const C& c1,const C& c2,P& p1,P& p2){
  D x1=c2.p.X-c1.p.X,y1=c2.p.Y-c1.p.Y;
  D r1=c1.r,r2=c2.r;
  D a=(x1*x1+y1*y1+r1*r1-r2*r2)/2.0;
  p1=P(((a*x1+y1*sqrt((x1*x1+y1*y1)*r1*r1-a*a))/(x1*x1+y1*y1))+c1.p.X,((a*y1-x1*sqrt((x1*x1+y1*y1)*r1*r1-a*a))/(x1*x1+y1*y1))+c1.p.Y);
  p2=P(((a*x1-y1*sqrt((x1*x1+y1*y1)*r1*r1-a*a))/(x1*x1+y1*y1))+c1.p.X,((a*y1+x1*sqrt((x1*x1+y1*y1)*r1*r1-a*a))/(x1*x1+y1*y1))+c1.p.Y);
}

ll N,K;
vector<ll> Xp,Yp,L;

bool ok(double T){
	vector<double> R(N);
	rep(i,N){
		R[i]=T/(double)L[i];
	}
	vector<P> cands;
	rep(i,N)rep(j,i){
		P p1,p2;
		C c1=C(P(Xp[i],Yp[i]),R[i]);
		C c2=C(P(Xp[j],Yp[j]),R[j]);
		int r=cRel(c1,c2);
		if(r!=ONE_OVER_CROSS&&r!=ONE_CONTAINED_CROSS&&r!=ONE_CROSS&&r!=TWO_CROSS)continue;
		crosspointCC(C(P(Xp[i],Yp[i]),R[i]),C(P(Xp[j],Yp[j]),R[j]),p1,p2);

		cands.push_back(p1);
		cands.push_back(p2);
	}
	rep(i,N){
		cands.push_back(P(Xp[i],Yp[i]));
	}
	rep(i,cands.size()){
		ll cnt=0;
		rep(j,N){
			if(pow(Xp[j]-cands[i].X,2)+pow(Yp[j]-cands[i].Y,2)<R[j]*R[j]+eps)cnt++;
		}
		if(cnt>=K)return true;
	}
	return false;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin>>N>>K;
  Xp.resize(N); Yp.resize(N); L.resize(N);

  rep(i,N){
  	cin>>Xp[i]>>Yp[i]>>L[i];
  }

  double lb=0,ub=1e9;
  rep(_,100){
  	double mid=(lb+ub)/2.0;
  	if(ok(mid)) ub=mid;
  	else lb=mid;
  }
  printf("%.10f\n", lb);

  return 0;
}