题目描述

给定 $n$ 个不共点的蹦床，第 $i$ 个蹦床的位置为 $(x_i, y_i)$，反弹力为 $p_i$。

存在整数 $S$。定义能从第 $i$ 个蹦床跳到第 $j$ 个蹦床当且仅当 $ p_i \times S \ge \lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert $。

你需要钦定一个起点，使得可以从该蹦床抵达所有蹦床（可以多步），并最小化 $S$，输出最小值。

输入格式

第一行输入 $N$

接下来每行输入三个整数分别代表 $x_i$ $y_i$ $P_i$

输出格式

输出一个整数代表答案

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

2

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

18

样例 1 解释

当 $S=2$，从第 $2$ 个点出发可以跳往其余所有点。

• 从 $2\to 1$，满足 $p_2\times S\geq dis(2\to 1)$
• 从 $2\to 3$，满足 $p_2\times S\geq dis(2\to 3)$
• 从 $2\to 4$，要经过两步，即 $2\to 3\to 4$。每一步分别满足 $p_2\times S\geq dis(2\to 3),\ p_3\times S\geq dis(3\to 4)$。

提示

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