跳跃高桥 2

题目描述

高桥君居住的二维平面城市中有 $N$ 个蹦床。第 $i$ 个蹦床位于点 $(x_i, y_i)$，具有 $P_i$ 的功率。高桥君的跳跃能力记为 $S$。初始时 $S=0$。高桥君每训练一次，$S$ 就增加 1。

当且仅当 $P_iS \ge |x_i - x_j| + |y_i - y_j|$ 时，高桥君可以从第 $i$ 个蹦床跳到第 $j$ 个蹦床。

高桥君的目标是能够选择一个起始蹦床，使得从该蹦床出发经过若干次跳跃可以到达任意一个蹦床。

为了实现目标，他至少需要训练多少次？

输入格式

输入按以下格式从标准输入给出：

N
x_1 y_1 P_1
⋮
x_N y_N P_N

输出格式

输出答案。

样例

4
-10 0 1
0 0 5
10 0 1
11 0 1

2

如果训练两次，则 $S=2$， 此时他从第 2 个蹦床出发可以到达任意一个蹦床。

例如，可以如下到达第 4 个蹦床。

从第 2 个蹦床跳到第 3 个蹦床。（因为 $P_2 S = 10$ 且 $|x_2-x_3| + |y_2-y_3| = 10$，满足 $P_2 S \ge |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 \ge |x_3-x_4| + |y_3-y_4|$。）

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

18

数据范围

• $2 \le N \le 200$
• $-10^9 \le x_i, y_i \le 10^9$
• $1 \le P_i \le 10^9$
• 若 $i \neq j$，则 $(x_i, y_i) \neq (x_j, y_j)$。
• 输入中的所有值均为整数。