题目描述

在 Takahashi 生活的一个二维平面城镇上有 $N$ 个蹦床。第 $i$ 个蹦床位于点 $(x_i, y_i)$，具有功率 $P_i$。Takahashi 的跳跃能力用 $S$ 表示。初始时，$S=0$。每次 Takahashi 训练，$S$ 增加 $1$。

当且仅当满足以下条件时，Takahashi 可以从第 $i$ 个蹦床跳到第 $j$ 个蹦床：

• $P_iS\\geq |x_i - x_j| +|y_i - y_j|$。

Takahashi 的目标是能够选择一个起始蹦床，以便他可以用一些跳跃从选定的蹦床达到任何一个蹦床。

他最少需要训练多少次才能达到他的目标？

约束条件

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

输入

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

$N$ $x_1$ $y_1$ $P_1$ $\\vdots$ $x_N$ $y_N$ $P_N$

输出

打印答案。

示例输入1

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

示例输出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|$。）

示例输入2

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

示例输出2

18