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:
#!/usr/bin/env python3
import sys
INF = float("inf")

tol = 1e-9


def ctc(x1, y1, r1, x2, y2, r2):
    # 二つの円の共通接線の数
    # common tangent count?
    # common tangent of circle?
    # 2円の関係性は、
    # 同一(=INF), 離れている(=4)、外接(=3)、交わる(=2)、内接(=1)、内包(=0)がある
    tol = 1e-9
    # r1 <= r2として一般性を失わない
    if r2 < r1:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        r1, r2 = r2, r1

    d = ((x1-x2)**2 + (y1-y2)**2)**0.5

    if x1 == x2 and y1 == y2 and d < tol:
        # 同一の円
        return INF
    elif (d - (r2+r1)) > tol:
        # 離れている
        return 4
    elif (d - (r2+r1)) > -tol:
        # 外接している
        return 3
    elif (d-(r2-r1)) > tol:
        # 交わっている
        return 2
    elif (d-(r2-r1)) > -tol:
        # 内接している
        return 1
    else:
        # 内包している
        return 0


def inner(x1, y1, c1, x2, y2, c2):
    coeff1 = c1/(c1+c2)
    coeff2 = c2/(c1+c2)
    b = (x1*coeff1+x2*coeff2, y1*coeff1+y2*coeff2)
    return b


def intersection(x1, y1, r1, x2, y2, r2):
    status = ctc(x1, y1, r1, x2, y2, r2)

    if not (1 <= status <= 3):
        return []
    elif status == 3:
        # 外接している場合
        return [inner(x1, y1, r1, x2, y2, r2)]
    elif status == 1:
        # 内接している場合
        return [(x1 + r1*(x1-x2)/d, y1 + r1*(y1-y2)/d)]
    else:
        # 交わっている場合
        L = ((x1-x2)**2 + (y1-y2)**2)**0.5
        cos = ((L**2+r1**2)-r2**2)/(2*r1*L)
        e1 = ((x2-x1)/L, (y2-y1)/L)
        e2 = (-(y2-y1)/L, (x2-x1)/L)
        P1H = ((r1*cos/L)*(x2-x1), (r1*cos/L)*(y2-y1))
        ah = (r1**2-(r1*cos)**2)**0.5
        HA = (e2[0]*ah, e2[1]*ah)
        A = (x1 + P1H[0]+HA[0], y1+P1H[1]+HA[1])
        B = (x1 + P1H[0]-HA[0], y1+P1H[1]-HA[1])
        return [A, B]


def circle_in(x, y, x1, y1, r1):
    tol = 1e-9
    L = (x1-x)**2 + (y1-y)**2
    R = r1**2
    LR = L-R

    if LR > tol:
        return False
    elif LR > -tol:
        return True
    else:
        return True


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[int]"):

    # 時刻Tの時点でK枚以上の肉が焼ける熱源の配置はあるか

    left = 0
    right = 2000*max(c)
    for _ in range(300):
        if right - left < tol:
            break
        mid = (left + right)/2
        yakiniku = 0
        for i in range(N):
            for j in range(i+1, N):
                b = intersection(x[i], y[i], mid/c[i], x[j], y[j], mid/c[j])
                for xx, yy in b:
                    count = [circle_in(xx, yy, x[k], y[k], mid/c[k])
                             for k in range(N)]
                    if yakiniku < sum(count):
                        yakiniku = max(yakiniku, sum(count))
        for i in range(N):
            count = [circle_in(x[i], y[i], x[k], y[k], mid/c[k])
                     for k in range(N)]
            if yakiniku < sum(count):
                yakiniku = max(yakiniku, sum(count))
        # print(left, right, mid)
        # for i in range(N):
        #     print("(x-({}))^2+(y-({}))^2=({})^2".format(
        #         x[i], y[i], mid/c[i]))
        if yakiniku >= K:
            right = mid
        else:
            left = mid

    print(mid)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()