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


def intersections(T, x1, y1, c1, x2, y2, c2):
    # 2つの円 (x - x_i)**2 + (y - y_i)**2 = (T/c_i)**2 の交点を求める
    left = ((c1 * c2)**2) * ((x1 - x2)**2 + (y1 - y2)**2)
    right = (T**2) * ((c1 + c2)**2)
    # 交点なし
    if left > right:
        return list()
    # 交点1つ
    if left == right:
        return [((c1*x1 + c2*x2) / (c1 + c2), (c1*y1 + c2*y2) / (c1 + c2))]
    # 交点2つ
    r1, r2 = T / c1, T / c2
    p12 = (x2 - x1, y2 - y1)
    coef = (r1**2 + p12[0]**2 + p12[1]**2 - r2**2) / (2 * (p12[0]**2 + p12[1]**2))
    p1h = (coef * p12[0], coef * p12[1])
    coef = (r1**2 - p1h[0]**2 - p1h[1]**2) / (p12[0]**2 + p12[1]**2)
    coef = math.sqrt(max(0, coef))  # 誤差を吸収
    hq1 = (- coef * p12[1], coef * p12[0])
    hq2 = (coef * p12[1], - coef * p12[0])
    return [
        (x1 + p1h[0] + hq1[0], y1 + p1h[1] + hq1[1]),
        (x1 + p1h[0] + hq2[0], y1 + p1h[1] + hq2[1])
    ]


def check(T, K, points):
    N = len(points)
    target_points = [(p[0], p[1]) for p in points]
    for pair in itertools.combinations(range(N), 2):
        p1 = points[pair[0]]
        p2 = points[pair[1]]
        target_points += intersections(T, p1[0], p1[1], p1[2], p2[0], p2[1], p2[2])
    for tp in target_points:
        cnt = 0
        for p in points:
            d2 = (tp[0] - p[0])**2 + (tp[1] - p[1])**2
            if d2 <= (T/p[2])**2 + 10**(-6):  # 誤差を吸収
                cnt += 1
            if cnt >= K:
                return True
    return False


def main():
    eps = 10 ** (-10)
    N, K = list(map(int, input().split()))
    points = [list(map(int, input().split())) for _ in range(N)]
    ng, ok = 0, 3 * (10**5)  # Time
    while ok - ng > eps:
        mid = (ok + ng) / 2
        if check(mid, K, points):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    main()