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 PYTHON3):

Solution:
import sys
readline = sys.stdin.buffer.readline
EPS = 1e-7
class Circle:
    def __init__(self, cx, cy, r):
        self.center = (cx, cy)
        self.radius = r
    def cross(self, C2):
        x1, y1 = self.center
        x2, y2 = C2.center
        R1 = self.radius
        R2 = C2.radius
        
        if (R2-R1)**2 + EPS <= (x2-x1)**2 + (y2-y1)**2 <= (R2+R1)**2 - EPS:
            dx, dy = x2-x1, y2-y1
            a = (R2**2 - R1**2 + x1**2 - x2**2 + y1**2 - y2**2)/2
            if abs(dy) > EPS:     
                #交点はdx*X + dy*Y + a = 0 上
                D = dx**2 + dy**2
                bx = a*dx+dx*dy*y1-x1*dy**2
                cx = dy**2*(x1**2-R1**2) + (a+dy*y1)**2
                cx1 = (-bx + (bx**2-D*cx)**0.5)/D
                cx2 = (-bx - (bx**2-D*cx)**0.5)/D
                cy1 = -(dx*cx1+a)/dy
                cy2 = -(dx*cx2+a)/dy
            else:
                k = (R1**2-R2**2+dx**2)/2/dx
                cx1 = cx2 = x1+k
                cy1 = y1 + (R1**2-k**2)**0.5
                cy2 = y1 - (R1**2-k**2)**0.5
                
                
                
                
            return [(cx1, cy1), (cx2, cy2)]
        else:
            return []
    
    def isinside(self, x, y):
        x1, y1 = self.center
        return (x1-x)**2 + (y1-y)**2 - EPS < self.radius**2

            
N, K = map(int, readline().split())
Points = [tuple(map(int, readline().split())) for _ in range(N)]

ok = 1e6
ng = 0
candidate = [(x, y) for x, y, _ in Points]
for _ in range(40):
    med = (ok+ng)/2
    Cs = [Circle(x, y, med/c) for x, y, c in Points]
    candidate2 = candidate[:]
    for i in range(N):
        for j in range(i):
            candidate2.extend(Cs[i].cross(Cs[j]))
    for px, py in candidate2:
        res = 0
        for C in Cs:
            if C.isinside(px, py):
                res += 1
        if res >= K:
            ok = med
            break
    else:
        ng = med


print(ok)