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 <bits/stdc++.h>
using namespace std ;
double x[100] , y[100] , c[100] , r[100];
const double esp = 1e-9 ;
typedef pair<double , double> Pair ;
int n , k ;
double get(Pair a , Pair b)
{
	return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)) ;
}
vector<Pair> calc(double x1 , double y1 , double r1 , double x2 , double y2 , double r2)
{
	 // x1 -= x2 , y1 -= y2 ;
	 // double t1 = (x1 * x1 + y1 * y1 + r2 * r2 - r1 * r1) / (2 * x1) ;
	 // double t2 = y1 / x1 ;
	 // double a = t2 * t2 , b = -2 * t1 * t2 , c = t1 * t1 - t2 * t2 ;
	 // double d = b * b - 4 * a * a ;
   // if(d < 0) return {} ;
	 // double c1 = (-b + sqrt(d)) / 2 / a ;
	 // double c2 = (-b - sqrt(d)) / 2 / a ;
	 // return {{t1 - t2 * c1 , c1} , {t1 - t2 * c2 , c2}} ;
	 x1-=x2,y1-=y2;
	 double S=x1*x1+y1*y1,a=(S+r2*r2-r1*r1)/2,D=S*r2*r2-a*a;
	 if(D<0) return {};
	 double A1=a*x1,B1=y1*sqrt(D);
	 double A2=a*y1,B2=x1*sqrt(D);
	 return {{(A1+B1)/S+x2,(A2-B2)/S+y2},{(A1-B1)/S+x2,(A2+B2)/S+y2}};
}
bool check(double t)
{
	vector<Pair> res ;
	for(int i = 1 ; i <= n ;i ++)  r[i] = t / c[i] ;
	for(int i = 1; i <= n ;i ++)
	{
		res.push_back({x[i] , y[i]}) ;
		for(int j = i + 1; j <= n ;j ++)
		{
		vector<Pair> p = calc(x[i] , y[i] , r[i] , x[j] , y[j] , r[j]) ;
		for(auto t : p)
		 res.push_back(t) ;
		}
	}

	for(auto tt : res)
	 {
		 int cnt = 0 ;
		 for(int i = 1 ;i <= n ;i ++)
		  if( get(tt , {x[i] , y[i]})  <= r[i] + esp ) cnt ++ ;
		if(cnt >= k) return true ;
	 }
	 return false ;

}
int main()
{
  scanf("%d%d" , &n , &k) ;
	for(int i = 1; i <= n ;i ++)
	 scanf("%lf%lf%lf" , &x[i] , &y[i] , &c[i]) ;
	double l = 0 , r = 1e9 ;
 for(int i = 0 ; i < 100 ;i ++ )
	 {
		 double mid = (l + r) / 2 ;
		 if(check(mid)) r = mid ;
		 else l = mid ;
	 }
	 printf("%.12lf\n" , r) ;
	return 0 ;
}