#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const double eps=1e-8;
inline int sgn(double n) {return fabs(n)<eps?0:(n<0?-1:1);}
inline double sqr(double x) {return x*x;}
inline double Sqrt(double a) {return a<=0?0:sqrt(a);}
int abs(int x) {return x>=0?x:-x;}
struct point
{
	double x,y;
	point(){}
	point(double a,double b):x(a),y(b){}
	friend point operator + (const point &a,const point &b)
	{
		return point(a.x+b.x,a.y+b.y);
	}
	friend point operator - (const point &a,const point &b)
	{
		return point(a.x-b.x,a.y-b.y);
	}
	friend bool operator == (const point &a,const point &b)
	{
		return (sgn(a.x-b.x)==0) && (sgn(a.y-b.y)==0);
	}
	friend point operator * (const point &a,const double &b)
	{
		return point(a.x*b,a.y*b);
	}
	friend point operator * (const double &a,const point &b)
	{
		return point(a*b.x,a*b.y);
	}
	friend point operator / (const point &a,const double &b)
	{
		return point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(sqr(x)+sqr(y));
	}
}po[70];
point rotate(const point &p,double cost,double sint)
{
	double x=p.x,y=p.y;
return point(x*cost-y*sint,x*sint+y*cost);
}
pair<point,point> crosspoint(point ap,double ar,point bp,double br)
{
	double d=(ap-bp).norm();
	double cost=(ar*ar+d*d-br*br)/(2.0*ar*d);
	double sint=sqrt(1.-cost*cost);
	point v=(bp-ap)/(bp-ap).norm()*ar;
return mp(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}
double dist(const point &a,const point &b){return (a-b).norm();}
int n,k,topt;
double c[70],ans,r[70];
point now[1000010];
bool ok(double tt)
{
	topt=0;
	for (int i=1;i<=n;i++) r[i]=tt/c[i],now[++topt]=po[i];
	for (int i=1;i<=n;i++)
	 for (int j=i+1;j<=n;j++)
	 if (-eps<=r[i]+r[j]-dist(po[i],po[j]))
	 {
	 	pair<point,point>co=crosspoint(po[i],r[i],po[j],r[j]);
	 	now[++topt]=co.fr; now[++topt]=co.sc;
	 }
	for (int i=1;i<=topt;i++)
	{
		int num=0;
		for (int j=1;j<=n;j++) if (-eps<=r[j]-dist(now[i],po[j])) num++;
		if (num>=k) return 1;
	}
return 0;
}
int main()
{
	//point aa,bb; aa=crosspoint({0,0},1,{1,0},1).fr; bb=crosspoint({0,0},1,{1,0},1).sc;
	//printf("%.8f %.8f\n%.8f %.8f\n",aa.x,aa.y,bb.x,bb.y);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&po[i].x,&po[i].y,&c[i]);
	double l=0,r=1e8; ans=r;
	for (int _=1;_<=150;_++)
	{
		double mid=(l+r)/2.0;
		if (ok(mid)) {ans=min(ans,mid); r=mid-1;}else l=mid+1;
	}
	printf("%.8f\n",ans);
return 0;
}
### Prompt

Please create a solution in cpp 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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const double eps=1e-8;
inline int sgn(double n) {return fabs(n)<eps?0:(n<0?-1:1);}
inline double sqr(double x) {return x*x;}
inline double Sqrt(double a) {return a<=0?0:sqrt(a);}
int abs(int x) {return x>=0?x:-x;}
struct point
{
	double x,y;
	point(){}
	point(double a,double b):x(a),y(b){}
	friend point operator + (const point &a,const point &b)
	{
		return point(a.x+b.x,a.y+b.y);
	}
	friend point operator - (const point &a,const point &b)
	{
		return point(a.x-b.x,a.y-b.y);
	}
	friend bool operator == (const point &a,const point &b)
	{
		return (sgn(a.x-b.x)==0) && (sgn(a.y-b.y)==0);
	}
	friend point operator * (const point &a,const double &b)
	{
		return point(a.x*b,a.y*b);
	}
	friend point operator * (const double &a,const point &b)
	{
		return point(a*b.x,a*b.y);
	}
	friend point operator / (const point &a,const double &b)
	{
		return point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(sqr(x)+sqr(y));
	}
}po[70];
point rotate(const point &p,double cost,double sint)
{
	double x=p.x,y=p.y;
return point(x*cost-y*sint,x*sint+y*cost);
}
pair<point,point> crosspoint(point ap,double ar,point bp,double br)
{
	double d=(ap-bp).norm();
	double cost=(ar*ar+d*d-br*br)/(2.0*ar*d);
	double sint=sqrt(1.-cost*cost);
	point v=(bp-ap)/(bp-ap).norm()*ar;
return mp(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}
double dist(const point &a,const point &b){return (a-b).norm();}
int n,k,topt;
double c[70],ans,r[70];
point now[1000010];
bool ok(double tt)
{
	topt=0;
	for (int i=1;i<=n;i++) r[i]=tt/c[i],now[++topt]=po[i];
	for (int i=1;i<=n;i++)
	 for (int j=i+1;j<=n;j++)
	 if (-eps<=r[i]+r[j]-dist(po[i],po[j]))
	 {
	 	pair<point,point>co=crosspoint(po[i],r[i],po[j],r[j]);
	 	now[++topt]=co.fr; now[++topt]=co.sc;
	 }
	for (int i=1;i<=topt;i++)
	{
		int num=0;
		for (int j=1;j<=n;j++) if (-eps<=r[j]-dist(now[i],po[j])) num++;
		if (num>=k) return 1;
	}
return 0;
}
int main()
{
	//point aa,bb; aa=crosspoint({0,0},1,{1,0},1).fr; bb=crosspoint({0,0},1,{1,0},1).sc;
	//printf("%.8f %.8f\n%.8f %.8f\n",aa.x,aa.y,bb.x,bb.y);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&po[i].x,&po[i].y,&c[i]);
	double l=0,r=1e8; ans=r;
	for (int _=1;_<=150;_++)
	{
		double mid=(l+r)/2.0;
		if (ok(mid)) {ans=min(ans,mid); r=mid-1;}else l=mid+1;
	}
	printf("%.8f\n",ans);
return 0;
}
```