#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-7
int N,K;
struct xy{
	int x;
	int y;
	int c;
};
double distance(double x,double y, xy k){
	return sqrt(pow(x-k.x,2)+pow(y-k.y,2));
}
bool niku_judge(double t,vector<xy> &niku){
	for (int i = 0; i < N; i++){
		for (int j = i; j < N; j++){
			if(i==j){
				int count=0;
				for (int k = 0; k < N; k++){
					if(distance(niku[i].x,niku[i].y,niku[k])<=t/niku[k].c)count++;
				}
				if(count>=K)return true;
			}else{
				double a=niku[j].x-niku[i].x;
				double b=niku[j].y-niku[i].y;
				bool b_zero=false;
				if(b==0){
					b=a;a=0;
					b_zero=true;
				}
				double c=-a/b;
				double d=(a*a+b*b+pow(t/niku[i].c,2)-pow(t/niku[j].c,2))/(2*b);
				double e=1+c*c;
				double f=2*c*d;
				double g=d*d-pow(t/niku[i].c,2);
				double x1;
				if(f*f-4*e*g<0)continue;
				if(f>0)x1=(-f-sqrt(f*f-4*e*g))/(2*e);
				else x1=(-f+sqrt(f*f-4*e*g))/(2*e);
				double x2=-x1-f/e;
				double y1=c*x1+d;
				double y2=c*x2+d;
				if(b_zero){
					swap(x1,y1);swap(x2,y2);
				}
				x1+=niku[i].x;x2+=niku[i].x;
				y1+=niku[i].y;y2+=niku[i].y;
				int count=0;
				for (int k = 0; k < N; k++){
					if(k==i||k==j)continue;
					if(distance(x1,y1,niku[k])<=t/niku[k].c)count++;
				}
				if(count>=K-2)return true;
				count=0;
				for (int k = 0; k < N; k++){
					if(k==i||k==j)continue;
					if(distance(x2,y2,niku[k])<=t/niku[k].c)count++;
				}
				if(count>=K-2)return true;
			}
		}
	}
	return false;
}
double bi_search(double l, double r, vector<xy> &niku){
	double m=(l+r)/2.0;
	if(niku_judge(m,niku)==false)return bi_search(m,r,niku);
	else if(niku_judge(m-eps,niku)==true)return bi_search(l,m,niku);
	else return m;
}
int main() {
	cin>>N>>K;
	vector<xy> niku(N);
	int x_max=0;int y_max=0;int c_max=0;
	for (int i = 0; i < N; i++){
		cin>>niku[i].x>>niku[i].y>>niku[i].c;
		x_max=max(x_max,abs(niku[i].x));
		y_max=max(y_max,abs(niku[i].y));
		c_max=max(c_max,abs(niku[i].c));
	}
	double t_max=(x_max+y_max)*c_max;
	printf("%.6f\n",bi_search(0,t_max,niku));
}
### 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
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-7
int N,K;
struct xy{
	int x;
	int y;
	int c;
};
double distance(double x,double y, xy k){
	return sqrt(pow(x-k.x,2)+pow(y-k.y,2));
}
bool niku_judge(double t,vector<xy> &niku){
	for (int i = 0; i < N; i++){
		for (int j = i; j < N; j++){
			if(i==j){
				int count=0;
				for (int k = 0; k < N; k++){
					if(distance(niku[i].x,niku[i].y,niku[k])<=t/niku[k].c)count++;
				}
				if(count>=K)return true;
			}else{
				double a=niku[j].x-niku[i].x;
				double b=niku[j].y-niku[i].y;
				bool b_zero=false;
				if(b==0){
					b=a;a=0;
					b_zero=true;
				}
				double c=-a/b;
				double d=(a*a+b*b+pow(t/niku[i].c,2)-pow(t/niku[j].c,2))/(2*b);
				double e=1+c*c;
				double f=2*c*d;
				double g=d*d-pow(t/niku[i].c,2);
				double x1;
				if(f*f-4*e*g<0)continue;
				if(f>0)x1=(-f-sqrt(f*f-4*e*g))/(2*e);
				else x1=(-f+sqrt(f*f-4*e*g))/(2*e);
				double x2=-x1-f/e;
				double y1=c*x1+d;
				double y2=c*x2+d;
				if(b_zero){
					swap(x1,y1);swap(x2,y2);
				}
				x1+=niku[i].x;x2+=niku[i].x;
				y1+=niku[i].y;y2+=niku[i].y;
				int count=0;
				for (int k = 0; k < N; k++){
					if(k==i||k==j)continue;
					if(distance(x1,y1,niku[k])<=t/niku[k].c)count++;
				}
				if(count>=K-2)return true;
				count=0;
				for (int k = 0; k < N; k++){
					if(k==i||k==j)continue;
					if(distance(x2,y2,niku[k])<=t/niku[k].c)count++;
				}
				if(count>=K-2)return true;
			}
		}
	}
	return false;
}
double bi_search(double l, double r, vector<xy> &niku){
	double m=(l+r)/2.0;
	if(niku_judge(m,niku)==false)return bi_search(m,r,niku);
	else if(niku_judge(m-eps,niku)==true)return bi_search(l,m,niku);
	else return m;
}
int main() {
	cin>>N>>K;
	vector<xy> niku(N);
	int x_max=0;int y_max=0;int c_max=0;
	for (int i = 0; i < N; i++){
		cin>>niku[i].x>>niku[i].y>>niku[i].c;
		x_max=max(x_max,abs(niku[i].x));
		y_max=max(y_max,abs(niku[i].y));
		c_max=max(c_max,abs(niku[i].c));
	}
	double t_max=(x_max+y_max)*c_max;
	printf("%.6f\n",bi_search(0,t_max,niku));
}
```