p02764 AtCoder Beginner Contest 157 - Yakiniku Optimization 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
```python
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    # 2円の中心間の距離の2乗
    def D2(x1,y1,x2,y2):
        return (x1-x2)**2+(y1-y2)**2

    # 2円が交点を持つか
    def check(R1,R2):
        x1,y1,r1 = R1
        x2,y2,r2 = R2
        d2 = D2(x1,y1,x2,y2)
        if (r1-r2)**2 < d2 <= (r1+r2)**2:
            return 1
        else:
            return 0

    # 2円の交点を出力
    def point(R1,R2):
        if not check(R1,R2):
            return []
        else:
            x1,y1,r1 = R1
            x2,y2,r2 = R2
            x2 -= x1
            y2 -= y1
            r = x2**2+y2**2
            a = (r+r1**2-r2**2)/2
            d = (r*r1**2-a**2)**0.5
            X,Y = a*x2/r, a*y2/r
            k = d/r
            X1,Y1 = X+y2*k+x1, Y-x2*k+y1
            X2,Y2 = X-y2*k+x1, Y+x2*k+y1
            return [(X1,Y1),(X2,Y2)]

    # 円に点が入っているか
    def inR(p,R):
        x2,y2 = p
        x1,y1,r1 = R
        d2 = D2(x1,y1,x2,y2)
        if d2 <= r1**2+1e-3:
            return 1
        else:
            return 0

    n,k = LI()
    p = LIR(n)
    l = 0
    r = 1000000
    while r-l > 1e-6:
        t = (l+r) / 2
        P = []
        for i in range(n):
            xi,yi,ci = p[i]
            ri = t/ci
            P.append((xi,yi))
            for j in range(i):
                xj,yj,cj = p[j]
                rj = t/cj
                ps = point((xi,yi,ri),(xj,yj,rj))
                for pi in ps:
                    P.append(pi)
        for pi in P:
            s = 0
            for x,y,c in p:
                r1 = t/c
                if inR(pi,(x,y,r1)):
                    s += 1
                if s >= k:
                    break
            if s >= k:
                r = t
                break
        else:
            l = t
    print(l)
    return

#Solve
if __name__ == "__main__":
    solve()

```