#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
最長距離の最小化
x秒でk枚以上焼けるか？
*/

double eps=1e-8;
ll n,k;
double x[61],y[61],c[61];

pair<pair<double,double>,pair<double,double>> kouten(pair<double,double> p1, pair<double,double> p2, double r1, double r2){
	double x1=p1.first, y1=p1.second, x2=p2.first, y2=p2.second;
	if(pow(x1-x2,2)+pow(y1-y2,2)>pow(r1+r2,2))return {{1e9,1e9},{1e9,1e9}};
	if(pow(x1-x2,2)+pow(y1-y2,2)<pow(r1-r2,2))return {{1e9,1e9},{1e9,1e9}};
	// if(x1==x2 && y1==y2)return {{1e9,1e9},{1e9,1e9}};
	if(abs(y1-y2)<eps){
		double x = (x2*x2-x1*x1+r1*r1-r2*r2)/2/(x2-x1);
		double a = sqrt(r1*r1-pow(x-x1,2));
		return {{x,y1+a},{x,y1-a}};
	}
	double a=-(x2-x1)/(y2-y1), b=(r1*r1-r2*r2-(x1*x1-x2*x2)-(y1*y1-y2*y2))/2/(y2-y1);
	double A=a*a+1, B=-x1+a*(b-y1), C=x1*x1+(b-y1)*(b-y1)-r1*r1;
	double X1 = (-B+sqrt(B*B-A*C))/A, X2 = (-B-sqrt(B*B-A*C))/A;
	double Y1 = a*X1+b, Y2 = a*X2+b;
	return {{X1,Y1},{X2,Y2}};
}

bool f(double t){
	int sum=0;
	rep(i,n){
		rep(j,i){
			auto p = kouten({x[i],y[i]},{x[j],y[j]},t/c[i],t/c[j]);
			double x1=p.first.first, y1=p.first.second, x2=p.second.first, y2=p.second.second;
			// printf("%d,%d = (%lf,%lf,%lf),(%lf,%lf,%lf)\n",i,j,x[i],y[i],t/c[i],x[j],y[j],t/c[j]);
			// printf("(%lf,%lf),(%lf,%lf)\n",i,j,x1,y1,x2,y2);
			if(x1!=1e9 && y1!=1e9){
				sum=0;
				rep(l,n)if(pow(x1-x[l],2)+pow(y1-y[l],2)<=pow(t/c[l],2)+eps)sum++;
				// cerr<<"1:"<<sum<<endl;
				if(sum>=k)return true;
				sum=0;
				rep(l,n)if(pow(x2-x[l],2)+pow(y2-y[l],2)<=pow(t/c[l],2)+eps)sum++;
				// cerr<<"2:"<<sum<<endl;
				if(sum>=k)return true;
			}
		}
	}
	rep(i,n){
		sum=0;
		rep(l,n)if(pow(x[i]-x[l],2)+pow(y[i]-y[l],2)<=pow(t/c[l],2)+eps)sum++;
		// cerr<<"3:"<<sum<<endl;
		if(sum>=k)return true;
	}
	return false;
}

void init(){
	cin>>n>>k;
	rep(i,n)cin>>x[i]>>y[i]>>c[i];
}

int main(void){
	init();
	double l=0,r=100*4000;
	while(r-l>eps){
		double mid=(r+l)/2;
		if(f(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<fixed<<setprecision(15)<<r<<endl;
	return 0;
}
### Prompt

Create a solution in Cpp for the following 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

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
最長距離の最小化
x秒でk枚以上焼けるか？
*/

double eps=1e-8;
ll n,k;
double x[61],y[61],c[61];

pair<pair<double,double>,pair<double,double>> kouten(pair<double,double> p1, pair<double,double> p2, double r1, double r2){
	double x1=p1.first, y1=p1.second, x2=p2.first, y2=p2.second;
	if(pow(x1-x2,2)+pow(y1-y2,2)>pow(r1+r2,2))return {{1e9,1e9},{1e9,1e9}};
	if(pow(x1-x2,2)+pow(y1-y2,2)<pow(r1-r2,2))return {{1e9,1e9},{1e9,1e9}};
	// if(x1==x2 && y1==y2)return {{1e9,1e9},{1e9,1e9}};
	if(abs(y1-y2)<eps){
		double x = (x2*x2-x1*x1+r1*r1-r2*r2)/2/(x2-x1);
		double a = sqrt(r1*r1-pow(x-x1,2));
		return {{x,y1+a},{x,y1-a}};
	}
	double a=-(x2-x1)/(y2-y1), b=(r1*r1-r2*r2-(x1*x1-x2*x2)-(y1*y1-y2*y2))/2/(y2-y1);
	double A=a*a+1, B=-x1+a*(b-y1), C=x1*x1+(b-y1)*(b-y1)-r1*r1;
	double X1 = (-B+sqrt(B*B-A*C))/A, X2 = (-B-sqrt(B*B-A*C))/A;
	double Y1 = a*X1+b, Y2 = a*X2+b;
	return {{X1,Y1},{X2,Y2}};
}

bool f(double t){
	int sum=0;
	rep(i,n){
		rep(j,i){
			auto p = kouten({x[i],y[i]},{x[j],y[j]},t/c[i],t/c[j]);
			double x1=p.first.first, y1=p.first.second, x2=p.second.first, y2=p.second.second;
			// printf("%d,%d = (%lf,%lf,%lf),(%lf,%lf,%lf)\n",i,j,x[i],y[i],t/c[i],x[j],y[j],t/c[j]);
			// printf("(%lf,%lf),(%lf,%lf)\n",i,j,x1,y1,x2,y2);
			if(x1!=1e9 && y1!=1e9){
				sum=0;
				rep(l,n)if(pow(x1-x[l],2)+pow(y1-y[l],2)<=pow(t/c[l],2)+eps)sum++;
				// cerr<<"1:"<<sum<<endl;
				if(sum>=k)return true;
				sum=0;
				rep(l,n)if(pow(x2-x[l],2)+pow(y2-y[l],2)<=pow(t/c[l],2)+eps)sum++;
				// cerr<<"2:"<<sum<<endl;
				if(sum>=k)return true;
			}
		}
	}
	rep(i,n){
		sum=0;
		rep(l,n)if(pow(x[i]-x[l],2)+pow(y[i]-y[l],2)<=pow(t/c[l],2)+eps)sum++;
		// cerr<<"3:"<<sum<<endl;
		if(sum>=k)return true;
	}
	return false;
}

void init(){
	cin>>n>>k;
	rep(i,n)cin>>x[i]>>y[i]>>c[i];
}

int main(void){
	init();
	double l=0,r=100*4000;
	while(r-l>eps){
		double mid=(r+l)/2;
		if(f(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<fixed<<setprecision(15)<<r<<endl;
	return 0;
}
```