#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return x != p.x? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};
typedef Point Vector;

struct Circle{
	Point center;
	double r;
};

int N,K;
Point point[65];
double C[65];
Circle circle[65];


double arg(Vector p){
	return atan2(p.y,p.x);
}

Vector polar(double a,double r){
	return Point(cos(r)*a,sin(r)*a);
}

double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

vector<Point> getCrossPoints(Circle c1,Circle c2){

	vector<Point> res;

	double d = abs(c1.center-c2.center);
	double a = acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
	double t = arg(c2.center-c1.center);

	res.push_back(Point(c1.center+polar(c1.r,t+a)));
	res.push_back(Point(c1.center+polar(c1.r,t-a)));

	return res;
}

double calc_dist(Point A,Point B){

	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}


//2つの円が2点で交わるか否か
bool is_Cross(Circle A,Circle B){

	double tmp_dist = calc_dist(A.center,B.center);

	return tmp_dist+EPS < A.r+B.r;
}

bool isOK(double len){


	vector<Point> V;

	for(int i = 0; i < N; i++){
		circle[i].center = point[i];
		circle[i].r = len/C[i];

		V.push_back(point[i]);
	}

	for(int i = 0; i < N-1; i++){
		for(int k = i+1; k < N; k++){
			if(!is_Cross(circle[i],circle[k]))continue;

			vector<Point> tmp =  getCrossPoints(circle[i],circle[k]);
			V.push_back(tmp[0]);
			V.push_back(tmp[1]);
		}
	}

	int count;

	for(int i = 0; i < V.size(); i++){

		count = 0;

		for(int k = 0; k < N; k++){
			if(calc_dist(circle[k].center,V[i]) <= circle[k].r+EPS){

				count++;
			}
		}
		if(count >= K)return true;
	}

	return false;
}


int main(){

	scanf("%d %d",&N,&K);

	for(int i = 0; i < N; i++){

		scanf("%lf %lf %lf",&point[i].x,&point[i].y,&C[i]);
	}

	double left = 0,right = 1000000,mid = (left+right)/2;
	double ans = 1000000;

	while(left+EPS < right){

		if(isOK(mid)){

			ans = mid;
			right = mid-EPS;
		}else{

			left = mid+EPS;
		}
		mid = (left+right)/2;
	}

	printf("%.10lf\n",ans);

	return 0;
}

### Prompt

Your task is to create 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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return x != p.x? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};
typedef Point Vector;

struct Circle{
	Point center;
	double r;
};

int N,K;
Point point[65];
double C[65];
Circle circle[65];


double arg(Vector p){
	return atan2(p.y,p.x);
}

Vector polar(double a,double r){
	return Point(cos(r)*a,sin(r)*a);
}

double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

vector<Point> getCrossPoints(Circle c1,Circle c2){

	vector<Point> res;

	double d = abs(c1.center-c2.center);
	double a = acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
	double t = arg(c2.center-c1.center);

	res.push_back(Point(c1.center+polar(c1.r,t+a)));
	res.push_back(Point(c1.center+polar(c1.r,t-a)));

	return res;
}

double calc_dist(Point A,Point B){

	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}


//2つの円が2点で交わるか否か
bool is_Cross(Circle A,Circle B){

	double tmp_dist = calc_dist(A.center,B.center);

	return tmp_dist+EPS < A.r+B.r;
}

bool isOK(double len){


	vector<Point> V;

	for(int i = 0; i < N; i++){
		circle[i].center = point[i];
		circle[i].r = len/C[i];

		V.push_back(point[i]);
	}

	for(int i = 0; i < N-1; i++){
		for(int k = i+1; k < N; k++){
			if(!is_Cross(circle[i],circle[k]))continue;

			vector<Point> tmp =  getCrossPoints(circle[i],circle[k]);
			V.push_back(tmp[0]);
			V.push_back(tmp[1]);
		}
	}

	int count;

	for(int i = 0; i < V.size(); i++){

		count = 0;

		for(int k = 0; k < N; k++){
			if(calc_dist(circle[k].center,V[i]) <= circle[k].r+EPS){

				count++;
			}
		}
		if(count >= K)return true;
	}

	return false;
}


int main(){

	scanf("%d %d",&N,&K);

	for(int i = 0; i < N; i++){

		scanf("%lf %lf %lf",&point[i].x,&point[i].y,&C[i]);
	}

	double left = 0,right = 1000000,mid = (left+right)/2;
	double ans = 1000000;

	while(left+EPS < right){

		if(isOK(mid)){

			ans = mid;
			right = mid-EPS;
		}else{

			left = mid+EPS;
		}
		mid = (left+right)/2;
	}

	printf("%.10lf\n",ans);

	return 0;
}

```