AT_abc257_d [ABC257D] Jumping Takahashi 2

高桥君居住的二维平面上的城市中有 $N$ 个跳板。第 $i$ 个跳板位于点 $(x_i, y_i)$，该跳板的力量为 $P_i$。高桥君的跳跃力用 $S$ 表示，初始时 $S=0$。每当高桥君进行一次训练，$S$ 就会增加 $1$。 只有在满足以下条件时，高桥君才能从第 $i$ 个跳板跳到第 $j$ 个跳板： - $P_i S \geq |x_i - x_j| + |y_i - y_j|$ 高桥君的目标是，选择一个合适的跳板作为起点，使得从该跳板出发，可以通过若干次跳跃到达任意一个跳板。 为了实现这个目标，高桥君最少需要进行多少次训练？

输入以如下格式从标准输入读入。 > $N$ > $x_1$ $y_1$ $P_1$ > $\vdots$ > $x_N$ $y_N$ $P_N$

请输出答案。

## 限制条件 - $2 \leq N \leq 200$ - $-10^9 \leq x_i, y_i \leq 10^9$ - $1 \leq P_i \leq 10^9$ - $(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)$ - 所有输入均为整数 ## 样例解释 1 如果高桥君进行了 $2$ 次训练，即 $S=2$，那么可以从第 $2$ 个跳板出发，到达所有跳板。例如，到达第 $4$ 个跳板的方法如下： - 从第 $2$ 个跳板跳到第 $3$ 个跳板。（$P_2 S = 10$，$|x_2-x_3| + |y_2-y_3| = 10$，满足 $P_2 S \geq |x_2-x_3| + |y_2-y_3|$。） - 从第 $3$ 个跳板跳到第 $4$ 个跳板。（$P_3 S = 2$，$|x_3-x_4| + |y_3-y_4| = 1$，满足 $P_3 S \geq |x_3-x_4| + |y_3-y_4|$。） 由 ChatGPT 4.1 翻译