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

Solution (in CPP):

Solution:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define eps 1e-9
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
	if(!x){putchar('0');return;}
	int top=0;
	while(x)stack[++top]=x%10,x/=10;
	while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
int n,m,X[110],Y[110],C[110];
inline double pf(double x){return x*x;}
inline bool pd(double x,double y,double limit)
{
	int ans=n;
	for(int i=1;i<=n;i++)if(sqrt(pf(X[i]-x)+pf(Y[i]-y))*C[i]-limit>eps)ans--;
	if(ans>=m)return true;
	else return false;
}
inline bool check(double limit)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			double r1=limit/C[i],r2=limit/C[j],dis=sqrt(pf(X[i]-X[j])+pf(Y[i]-Y[j]));
			int p1=i,p2=j;
			if(r1<r2)swap(r1,r2),swap(p1,p2);
			if(r1-dis-r2>eps)
			{
				if(pd(X[p2],Y[p2],limit)==true)return true;
			}
			else if(r1+r2-dis>eps)
			{
				double uf=(pf(r1)-pf(r2)+pf(dis))/(2.0*dis),x0=X[p1]+uf/dis*(X[p2]-X[p1]),y0=Y[p1]+uf/dis*(Y[p2]-Y[p1]);
				double ul=sqrt(pf(r1)-pf(uf));
				if(pd(x0-ul/dis*(Y[p2]-Y[p1]),y0+ul/dis*(X[p2]-X[p1]),limit)==true)return true;
				if(pd(x0+ul/dis*(Y[p2]-Y[p1]),y0-ul/dis*(X[p2]-X[p1]),limit)==true)return true;
			}
		}
	}return false;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)X[i]=read(),Y[i]=read(),C[i]=read();
    if(m==1){puts("0");return 0;}
    double l=0,r=300000,ans;
	while(r-l>eps)
	{
		double mid=(l+r)/2.0;
		if(check(mid)==true)ans=mid,r=mid;
		else l=mid;
	}printf("%.7lf\n",ans);
    return 0;
}