問題文

二次元平面上の宇宙に $1$ 個の恒星と $1,2,\dots,N$ の番号が付いた $N$ 個の惑星があります。

恒星は常に座標 $(0,0)$ にありますが、惑星 $i$ $(1 \leq i \leq N)$ は最初座標 $(X_{i}, Y_{i})$ に位置し、
$T_{i}$ 年ごとに反時計回りに一回転する角速度で、先の恒星を中心とした半径・角速度一定の円運動を行います。

ただし、異なる $2$ 個の惑星が同じ座標となった場合でも衝突は起きず、上記の軌道は変化しないものとします。

魔法使いのコアさんの目的は、転移魔法を使い、$0$ 個以上の惑星を経由して惑星 $1$ から惑星 $N$ へ移動することです。

コアさんの魔法レベルは整数 $s$ で表され、最初 $s=0$ です。コアさんが訓練を $1$ 回行う度に $s$ は $1$ 増加します。
そして、次の条件を満たすならば、またその場合に限り、コアさんは惑星 $i$ から惑星 $j$ $(1 \leq i,j \leq N \text{ かつ } i \neq j)$ に直接移動できます。

• 惑星 $i, j$ 間のユークリッド距離の取り得る最小値が $\sqrt{s}$ 以下である。

「ユークリッド距離」の定義（クリックで展開）

二次元平面上の任意の $2$ 点 $P_{1} ( x_{1}, y_{1} )$, $P_{2} ( x_{2}, y_{2} )$ について、
これら $2$ 点間のユークリッド距離 $L^{2} (P_{1}, P_{2} )$ は次のように定義されます。

• $L^{2} (P_{1}, P_{2} ) := \sqrt{ (x_{1}-x_{2})^{2} + (y_{1}-y_{2})^{2} }$

コアさんが先の目的を達成するためには、最小で何回の訓練を行う必要がありますか？

制約

• $2 \leq N \leq 800$

• $-2 \times 10^{4} \leq X_{i}, Y_{i} \leq 2 \times 10^{4}$ $(1 \leq i \leq N)$

• $(X_{i}, Y_{i}) \neq (0, 0)$ $(1 \leq i \leq N)$

• $(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ $(1 \leq i < j \leq N)$

• $1 \leq T_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$X_{1}$ $Y_{1}$ $T_{1}$
$X_{2}$ $Y_{2}$ $T_{2}$
     $\vdots$
$X_{N}$ $Y_{N}$ $T_{N}$

• $1$ 行目には $N$ が与えられる

• $(1 + i)$ $(1 \leq i \leq N)$ 行目には $X_{i}, Y_{i}, T_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力してください。

サンプル

3
1 1 3
0 3 4
-5 -5 3

17

4
10 10 100
-1 -1 100
-5 -5 100
3 3 100

98

2
4 3 2
-5 0 5

0

2
20000 20000 1000000000
-20000 -20000 1000000000

3200000000