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:
from math import atan2, cos, sin

EPS = 1e-7


def hypot(a):
    return sum(x ** 2 for x in a) ** 0.5


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def add(a, b):
    return [a[0] + b[0], a[1] + b[1], a[2] + b[2]]


def sub(a, b):
    return [a[0] - b[0], a[1] - b[1], a[2] - b[2]]


def matmul(mat, v):
    return [dot(row, v) for row in mat]


def rotZ(theta):
    return [[cos(theta), -sin(theta), 0], [sin(theta), cos(theta), 0], [0, 0, 1]]


def _circleCircleIntersection(R, d, r):
    # For circles centered at (0, 0) and (d, 0) with radius R and r respectively
    # Equations are:
    #   x^2       + y^2 = R^2
    #   (x - d)^2 + y^2 = r^2
    # Subtracting and expanding:
    #   x^2 - (x^2 - 2 * d * x + d^2) = R^2 - r^2
    #                 2 * d * x - d^2 = R^2 - r^2
    #                               x = (R^2 - r^2 + d^2) / (2*d)
    if d == 0:
        return [(0, 0)]
    x = (R ** 2 - r ** 2 + d ** 2) / (2 * d)
    ySq = R ** 2 - x ** 2
    if ySq == 0:
        return [(x, 0)]
    elif ySq > 0:
        y = ySq ** 0.5
        # assert abs((x ** 2 + y ** 2) - R ** 2) < EPS
        # assert abs(((x - d) ** 2 + y ** 2) - r ** 2) < EPS
        return [(x, y), (x, -y)]
    else:
        raise AssertionError()


def circleCircleIntersection(x1, y1, r1, x2, y2, r2):
    # Either 1 point, 2 points
    # 0 points because one circle contains the other
    # 0 points because the circles don't intersect
    v1 = [x1, y1, 0]
    v2 = [x2, y2, 0]
    d = hypot(sub(v2, v1))
    if r1 + r2 < d:
        # Circles don't intersect
        return []
    if min(r1, r2) + d < max(r1, r2):
        # One circle contains the other
        return []

    # Translate
    offset = list(v1)
    v1 = sub(v1, offset)
    v2 = sub(v2, offset)
    assert v1[0] == 0 and v1[1] == 0

    # Rotate
    angle = -atan2(v2[1], v2[0])
    v2 = matmul(rotZ(angle), v2)
    assert abs(v2[1]) < EPS

    ret = []
    for pt in _circleCircleIntersection(r1, v2[0], r2):
        pt = [pt[0], pt[1], 0]
        # Un-rotate
        pt = matmul(rotZ(-angle), pt)
        # Un-translate
        pt = add(pt, offset)
        ret.append((pt[0], pt[1]))

    return ret


N, K = list(map(int, input().split()))
XYC = []
for i in range(N):
    XYC.append(list(map(int, input().split())))


def numMeat(t):
    # At time t, each x, y can be heated by anything within a circle of radius radius t/c
    # Gather all intersecting points, some of which must be part of the region with most overlaps
    intersect = []
    for i in range(len(XYC)):
        x1, y1, c1 = XYC[i]
        r1 = t / c1
        for j in range(i + 1, len(XYC)):
            x2, y2, c2 = XYC[j]
            r2 = t / c2
            pts = circleCircleIntersection(x1, y1, r1, x2, y2, r2)
            intersect.extend(pts)
        intersect.append((x1, y1))

    best = 0
    for pt in intersect:
        count = 0
        for x, y, c in XYC:
            if c * ((x - pt[0]) ** 2 + (y - pt[1]) ** 2) ** 0.5 <= t + EPS:
                count += 1
        best = max(best, count)

    return best


lo = 0
# Get upperbound (by arbitrarily placing heat source at origin)
hi = max(c * (x ** 2 + y ** 2) ** 0.5 for x, y, c in XYC)
while hi - lo > EPS:
    mid = (hi + lo) / 2
    if numMeat(mid) >= K:
        hi = mid
    else:
        lo = mid
print(hi)