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 cmath
EPS = 1e-8

#cmath.rect(r, th) 極座標→直交座標
#cmath.polar(c) 複素数→極座標
#print("{:.12f}.format(hoge)") 桁数指定

n, k = map(int, input().split())
d = []
for _ in range(n):
	x, y, c = list(map(int, input().split()))
	d.append((complex(x, y), c))

ok, ng = 10**6, 0
for _ in range(60):
	t = (ok+ng)/2
	#t = 2.41

	res = 1
	#wrapped = [1 for _ in range(n)]
	for i in range(n):
		o1, r1 = d[i][0], t / d[i][1]
		cnt0 = 1
		for j in range(n):
			if j == i:
				continue
			o2, r2 = d[j][0], t / d[j][1]
			if abs(o1 - o2) + EPS <= r2:
				cnt0 += 1

		res = max(res, cnt0)
		for j in range(i+1, n):
			o2, r2 = d[j][0], t / d[j][1]
			if abs(o1 - o2) - EPS >= r1 + r2:
				#print(i, j)
				continue
			elif abs(o1 - o2) + min(r1, r2) + EPS <= max(r1, r2):
				continue
			else:
				co = (r1**2 - r2**2 + abs(o1 - o2)**2) / (2 * abs(o1 - o2) * r1)
				si = cmath.sqrt(1 - co**2)
				p1 = o1 + (o2 - o1) * (co + 1j * si) * r1 / abs(o1 - o2)
				p2 = o1 + (o2 - o1) * (co - 1j * si) * r1 / abs(o1 - o2)				#print(i, j, p1, p2)

			cnt1, cnt2 = 2, 2
			for l in range(n):
				if l == i or l == j:
					continue
				else:
					o3, r3 = d[l][0], t / d[l][1]
					if abs(p1 - o3) + EPS <= r3:
						cnt1 += 1
					if abs(p2 - o3) + EPS <= r3:
						cnt2 += 1
			#print(i, j, cnt1, cnt2)
			res = max(res, cnt1, cnt2)

	#res = max(res, max(wrapped))
	if res >= k:
		ok = t
	else:
		ng = t

if ok < 1e-6:
	print(0)
else:
	print(ok)