F - 烤肉优化问题

得分：600分

问题描述

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

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

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

限制

• 输入中的所有值都是整数。
• $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$

输入

从标准输入中按以下格式输入：

$N$ $K$

$x_1$ $y_1$ $c_1$

$\vdots$

$x_N$ $y_N$ $c_N$

输出

输出答案。

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