题目描述

Takahashi想要在一个烤网上烤$N$块肉，这个网可以看作一个二维平面。第$i$块肉的坐标是$(x_i,y_i)$，硬度为$c_i$;。

Takahashi可以使用一个热源来烤肉。如果他将热源放在坐标$(X,Y)$上，其中$X$和$Y$是实数，第$i$块肉将在$c_i \sqrt{{(\text{X}-x_i)}^2+{(\text{Y}-y_i)}^2}$秒后可以食用。

Takahashi想要吃$K$块肉。找到放置热源以最小化所需时间的方案，使得至少有$K$块肉可以食用。

输入

第一行输入两个整数$N,K$ 接下来一共$N$行，每行三个整数$x_i,y_i,c_i$

输出

输出答案。

如果与我们的答案的绝对或相对误差不超过$10^{-6}$ ，则算作正确。

4 3
-1 0 3
0 0 3
1 0 2
1 1 40

2.4

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

7411.2252

提示

• $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$