#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
#define pb push_back
#define fi first
#define se second 


typedef long double ld ;
struct pt {
	ld x,y; 
	pt operator+(pt p) {return {x+p.x, y+p.y};}
	pt operator-(pt p) {return {x-p.x, y-p.y};}
	pt operator*(ld d) {return {x*d, y*d};}
	pt operator/(ld d) {return {x/d, y/d};}
};
ostream& operator<<(ostream& os, pt p) {
	return os << "("<< p.x << "," << p.y << ")";
}
vector<pt>intrsct;
pt perp(pt p) {return {-p.y, p.x};}
ld sq(pt p){return p.x*p.x + p.y*p.y;}
bool prnt;
ld ds(pt p){
	return hypot(p.x,p.y);
}
void circleCircle(pt o1, ld r1, pt o2, ld r2) {
	pt d=o2-o1;
	double d2=sq(d);
	if (d2 == 0) {return ;} // concentric circles	
	double pd = (d2 + r1*r1 - r2*r2)/2; // = |O_1P| * d
	double h2 = r1*r1 - pd*pd/d2; // = hˆ2
	if (h2 >= 0) {
		pt p = o1 + d*pd/d2, h = perp(d)*sqrt(h2/d2);
		if(prnt){
			cout<<o1<<" "<<o2<<endl;
			cout<<r1<<" "<<r2<<endl;
			cout<<p<<" "<<h<<endl;
			cout<<p-h<<" "<<p+h<<endl;
			cout<<ds(p+h-o1)<<" "<<ds(p+h-o2)<<endl;
			cout<<ds(p-h-o1)<<" "<<ds(p-h-o2)<<endl;
			cout<<"-------------------------"<<endl;
			
		}
		intrsct.pb(p+h);
		intrsct.pb(p-h);
	}
}
pt c[66];
ld r[66];
ld rr[66];
int n,k;
bool ch(ld x){
	prnt = false;
	for(int i=0;i<n;i++){
		rr[i] = x/r[i];
	}
	intrsct.clear();
	for(int i=0;i<n;i++){
		intrsct.pb(c[i]);
		for(int j=0;j<n;j++){
			circleCircle(c[i],rr[i],c[j],rr[j]);
		}
	}
	for(pt p:intrsct){
		int cnt = 0;
		for(int i=0;i<n;i++){
			if(ds(p-c[i])<=rr[i]+1e-9)cnt++;
		}
		if(cnt>=k)return true;
	}
	return false;
}
void chh(ld x){
	prnt = true;
	cout<<"CHK "<<x<<endl;
	for(int i=0;i<n;i++){
		rr[i] = x/r[i];
		cout<<rr[i]<<" ";
	}
	cout<<endl;
	intrsct.clear();
	for(int i=0;i<n;i++){
		intrsct.pb(c[i]);
		for(int j=0;j<n;j++){
			circleCircle(c[i],rr[i],c[j],rr[j]);
//			pt p1 = intrsct.back();
		}
	}
	for(pt p:intrsct){
		cout<<p<<" : "<<endl;;
		int cnt = 0;
		for(int i=0;i<n;i++){
			cout<<i<<" ";
			cout<<ds(p-c[i])<<" "<<rr[i]<<endl;
			if(ds(p-c[i])<=rr[i]+1e-9)cnt++;
		}
		cout<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cout<<fixed<<setprecision(14);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		ld x,y; 
		cin>>x>>y;
		c[i] = {x,y};
		cin>>r[i];
	}
	ld ans = 0;
	if(k==1){
		cout<<ans<<endl;
		return 0;
	}
	ld st = 0;
	ld en = 1e12;
	for(int i=0;i<200;i++){
		ld mid = (st+en)/2;
		if(ch(mid)){
			en = mid;
		}else{
			st = mid;
		}
		
	}
	cout<<st<<endl;
	return 0;
}

### Prompt

Generate a cpp solution to 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 pb push_back
#define fi first
#define se second 


typedef long double ld ;
struct pt {
	ld x,y; 
	pt operator+(pt p) {return {x+p.x, y+p.y};}
	pt operator-(pt p) {return {x-p.x, y-p.y};}
	pt operator*(ld d) {return {x*d, y*d};}
	pt operator/(ld d) {return {x/d, y/d};}
};
ostream& operator<<(ostream& os, pt p) {
	return os << "("<< p.x << "," << p.y << ")";
}
vector<pt>intrsct;
pt perp(pt p) {return {-p.y, p.x};}
ld sq(pt p){return p.x*p.x + p.y*p.y;}
bool prnt;
ld ds(pt p){
	return hypot(p.x,p.y);
}
void circleCircle(pt o1, ld r1, pt o2, ld r2) {
	pt d=o2-o1;
	double d2=sq(d);
	if (d2 == 0) {return ;} // concentric circles	
	double pd = (d2 + r1*r1 - r2*r2)/2; // = |O_1P| * d
	double h2 = r1*r1 - pd*pd/d2; // = hˆ2
	if (h2 >= 0) {
		pt p = o1 + d*pd/d2, h = perp(d)*sqrt(h2/d2);
		if(prnt){
			cout<<o1<<" "<<o2<<endl;
			cout<<r1<<" "<<r2<<endl;
			cout<<p<<" "<<h<<endl;
			cout<<p-h<<" "<<p+h<<endl;
			cout<<ds(p+h-o1)<<" "<<ds(p+h-o2)<<endl;
			cout<<ds(p-h-o1)<<" "<<ds(p-h-o2)<<endl;
			cout<<"-------------------------"<<endl;
			
		}
		intrsct.pb(p+h);
		intrsct.pb(p-h);
	}
}
pt c[66];
ld r[66];
ld rr[66];
int n,k;
bool ch(ld x){
	prnt = false;
	for(int i=0;i<n;i++){
		rr[i] = x/r[i];
	}
	intrsct.clear();
	for(int i=0;i<n;i++){
		intrsct.pb(c[i]);
		for(int j=0;j<n;j++){
			circleCircle(c[i],rr[i],c[j],rr[j]);
		}
	}
	for(pt p:intrsct){
		int cnt = 0;
		for(int i=0;i<n;i++){
			if(ds(p-c[i])<=rr[i]+1e-9)cnt++;
		}
		if(cnt>=k)return true;
	}
	return false;
}
void chh(ld x){
	prnt = true;
	cout<<"CHK "<<x<<endl;
	for(int i=0;i<n;i++){
		rr[i] = x/r[i];
		cout<<rr[i]<<" ";
	}
	cout<<endl;
	intrsct.clear();
	for(int i=0;i<n;i++){
		intrsct.pb(c[i]);
		for(int j=0;j<n;j++){
			circleCircle(c[i],rr[i],c[j],rr[j]);
//			pt p1 = intrsct.back();
		}
	}
	for(pt p:intrsct){
		cout<<p<<" : "<<endl;;
		int cnt = 0;
		for(int i=0;i<n;i++){
			cout<<i<<" ";
			cout<<ds(p-c[i])<<" "<<rr[i]<<endl;
			if(ds(p-c[i])<=rr[i]+1e-9)cnt++;
		}
		cout<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cout<<fixed<<setprecision(14);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		ld x,y; 
		cin>>x>>y;
		c[i] = {x,y};
		cin>>r[i];
	}
	ld ans = 0;
	if(k==1){
		cout<<ans<<endl;
		return 0;
	}
	ld st = 0;
	ld en = 1e12;
	for(int i=0;i<200;i++){
		ld mid = (st+en)/2;
		if(ch(mid)){
			en = mid;
		}else{
			st = mid;
		}
		
	}
	cout<<st<<endl;
	return 0;
}

```