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
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

EPS = 1e-9


class Vector:
    x = 0
    y = 0

    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, other):
        return self.__class__(self.x+other.x, self.y+other.y)

    def __sub__(self, other):
        return self.__class__(self.x-other.x, self.y-other.y)

    def __mul__(self, other):
        return self.__class__(self.x*other, self.y*other)

    def sqrtNorm(self):
        return self.x*self.x+self.y*self.y

    def norm(self):
        return math.sqrt(self.sqrtNorm())


class Circle:
    v = Vector()
    r = 0

    def __init__(self, v, r):
        self.v = v
        self.r = r

    def get_intersections(self, c):
        v = c.v-self.v
        l = v.norm()
        # 円が重なっている
        if equal(l, 0):
            return []
        # 交点が一つ
        if equal(l+self.r+c.r, max(l, self.r, c.r)*2):
            if equal(l+self.r, c.r):
                return [self.v - v*(self.r/l)]
            else:
                return [self.v + v*(self.r/l)]
        # 遠距離で交点が存在しない
        if l+self.r+c.r < max(l, self.r, c.r)*2:
            return []

        x = (l*l + self.r*self.r - c.r*c.r) / (2*l)
        y = math.sqrt(self.r*self.r - x*x)
        mid = self.v + v * (x/l)
        rv = Vector(v.y, -v.x)
        return [mid+rv*(y/l), mid-rv*(y/l)]

    def is_inside(self, v):
        return (v-self.v).norm() < self.r+EPS


def equal(a, b):
    return abs(a-b) < EPS


def main():
    n, k = map(int, input().split())

    if k == 1:
        print(0)
        return

    cs = [None]*n
    rs = [0]*n
    for i in range(n):
        x, y, c = map(int, input().split())
        cs[i] = Circle(Vector(x, y), c)
        rs[i] = c
    l = 0
    r = 400000
    for z in range(100):
        x = (l+r)/2
        ps = [None]*n
        for i in range(n):
            ps[i] = cs[i].v

        for i in range(n):
            a = cs[i]
            a.r = x/rs[i]
            for j in range(i+1, n):
                b = cs[j]
                b.r = x/rs[j]
                ps += a.get_intersections(b)
        is_ok = False
        for p in ps:
            cnt = 0
            for i in range(n):
                nc = cs[i]
                nc.r = x/rs[i]
                if nc.is_inside(p):
                    cnt += 1
            if cnt >= k:
                is_ok = True
                break
        if is_ok:
            r = x
        else:
            l = x
    print(r)


main()