题目描述

高橋君が住んでいる二次元平面上の街には $N$ 個のジャンプ台があります。$i$ 番目のジャンプ台は点 $(x_i,\ y_i)$ にあり、ジャンプ台のパワーは $P_i$ です。また高橋君のジャンプ力は $S$ で表され、はじめ $S=0$ です。高橋君が訓練を $1$ 回行う度に $S$ は $1$ 増えます。

高橋君は以下の条件を満たす場合に限り、$i$ 番目のジャンプ台から $j$ 番目のジャンプ台にジャンプすることができます。

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

高橋君の目的は、適切に始点とするジャンプ台を決めることで、そのジャンプ台からどのジャンプ台にも何回かのジャンプで移動できるようにすることです。

目的を達成するためには高橋君は最低で何回訓練を行う必要があるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定 $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$，输出最小值。

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

提示

制約

• $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)$
• 入力は全て整数

Sample Explanation 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|$ を満たす。）