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
import cmath
import math
import copy
INF = float("inf")

EPS = 1e-9


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

    d = abs(p1-p2)

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


def inner(p1, c1, p2, c2):
    coeff1 = c1/(c1+c2)
    coeff2 = c2/(c1+c2)
    return p1*coeff1+p2*coeff2


def intersection(p1, r1, p2, r2):
    status = ctc(p1, r1, p2, r2)
    d = abs(p1-p2)
    if not (1 <= status <= 3):
        return []
    elif status == 3:           # 外接
        return [inner(p1, r1, p2, r2)]
    elif status == 1:           # 内接
        return [p1 + r1*(p1-p2)/d]
    else:                       # 交わっている場合
        if r1 > r2:
            p1, p2 = p2, p1
            r1, r2 = r2, r1
        d = abs(p1-p2)
        cos = (r1**2+d**2-r2**2)/(2*r1*d)
        angle = math.acos(cos)
        phi = cmath.phase(p2-p1)
        return [
            p1 + cmath.rect(r1, phi+angle),
            p1 + cmath.rect(r1, phi-angle)
        ]


def circle_in(p, o, r1, allow_on_edge=True):
    if allow_on_edge:
        return abs(o-p)-r1 < EPS
    else:
        return abs(o-p)-r1 < -EPS


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

    # 時刻Tの時点でK枚以上の肉が焼ける熱源の配置はあるか
    comp = [complex(xx, yy) for xx, yy in zip(x, y)]

    left = 0
    right = 2000*max(c)
    while right - left > EPS:
        mid = (left + right)/2
        yakiniku = 0
        b = copy.copy(comp)
        for i in range(N):
            for j in range(i+1, N):
                b.extend(intersection(comp[i], mid/c[i], comp[j], mid/c[j]))

        for p in b:
            count = [circle_in(p, comp[k], mid/c[k])
                     for k in range(N)]
            yakiniku = max(yakiniku, sum(count))
        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()