Problem Statement

高橋ノルム君の可能性は無限大です。高橋ノルムという名前の人物はこの世界にたくさんいます。

$2$ 次元平面上に $N$ 人の高橋ノルム君がいます。$i(1≦i≦N)$ 人目の高橋ノルム君は座標 $(x_i,y_i)$ にいます。 各高橋ノルム君には正整数定数 $c_i$ が割り当てられており、$i$ 人目の高橋ノルム君がある点 $(X,Y)$ に移動するためには $c_i*$max$(\|x_i-X|,\|y_i-Y\|)$ の時間がかかります。

あなたの仕事は、全ての高橋ノルム君が一点に集まるために必要な最小の時間を求めることです。 ここで、一点に集まるために必要な最小の時間とは最も遅くその点に到着する高橋君の移動にかかった時間とします。

高橋ノルム君は一斉に動き出し、お互いに干渉せず動くものとします。

Input

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

N
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N

• $1$ 行目には、高橋ノルム君の数を表す整数 $N (2≦N≦1,000)$ が与えられる。
• $2$ 行目からの $N$ 行のうち $i (1≦i≦N)$ 行目には、$i$ 人目の高橋君の二次元平面上の位置と定数を表す $3$ つの整数 $x_i,y_i,c_i (-10^5≦x_i,y_i≦10^5,1≦c_i≦1,000)$ が空白区切りで与えられる。
• 同じ座標に複数の高橋ノルム君がいることもあります。

部分点

この問題には部分点が設定されている。

• 任意の $i(1≦i≦N)$ について、$c_i=1$ を満たすデータセットに正解した場合は、$30$ 点が与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に $70$ 点が与えられる。

Output

全ての高橋ノルム君が一点に集まるために必要な最小の時間を出力せよ。 絶対誤差または相対誤差が $10^{−4}$ 以下ならば正解となる。 出力の末尾には改行を入れること。