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
import math

eps = 10**(-9)

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    circles = []
    C = []
    for _ in range(N):
        x, y, c = map(int, input().split())
        circles.append(Circle(Vector(x, y), c))
        C.append(c)

    def calc_meet(t):
        '''t秒後に焼ける肉の数の最大値を求める。
        '''
        # 候補点の列挙(交点と中心)
        candidates = []
        for i in range(N):
            candidates.append(circles[i].c)
            circles[i].r = t/C[i]
            for j in range(i+1, N):
                circles[j].r = t/C[j]
                candidates += circles[i].cp(circles[j])

        # t秒で焼ける肉の数の最大値を調べる
        m = 0
        for c in candidates:
            count = 0
            for i, meet in enumerate(circles):
                if (c - meet.c).length() * C[i] <= t + eps: count += 1
            m = max(m, count)

        return m

    under = 0
    r = 10**6
    while r-under>10**(-6):
        m = (r + under) / 2
        if calc_meet(m) >= K: r = m
        else: under = m
    print(r)
    
class Circle:
    def __init__(self, c, r):
        self.c, self.r = c, r
    
    def cp(self, other):
        v = other.c - self.c
        d = v.length()
        equal = lambda x,y: abs(x-y) < eps
        if equal(d, 0): return []
        if equal(sum([d, self.r, other.r]), 2 * max(d, self.r, other.r)):
            return [self.c + v*(self.r/d)]
        if sum([d, self.r, other.r]) < 2 * max(d, self.r, other.r): return [] #三角形ができない
        x = (d*d + self.r*self.r - other.r*other.r) / (2*d)
        h = math.sqrt(self.r*self.r - x*x)
        m = self.c + v*(x/d)
        return [m + v.rotate90()*(h/d), m - v.rotate90()*(h/d)]

class Vector:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def length(self): return math.sqrt(self.x*self.x + self.y*self.y)
    def rotate90(self): return Vector(self.y, -self.x)

    def __iadd__(self, other):
        self.x += other.x
        self.y += other.y
        return self
    def __add__(self, other):
        new_obj = Vector(self.x, self.y)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.x -= other.x
        self.y -= other.y
        return self
    def __sub__(self, other):
        new_obj = Vector(self.x, self.y)
        new_obj -= other
        return new_obj

    def __imul__(self, other_scalar):
        self.x *= other_scalar
        self.y *= other_scalar
        return self
    def __mul__(self, other_scalar):
        new_obj = Vector(self.x, self.y)
        new_obj *= other_scalar
        return new_obj

if __name__ == '__main__':
    main()