問題文

$xy$ 平面上に $N$ 個の点があり、それぞれの点に重みがついています。
$i$ 個目の点の座標は $(X_i,Y_i)$ で、重みは $C_i$ です。

$N$ 点の中から $4$ 点を選んで、それらを頂点とする面積が正の等脚台形を作ります。
このとき、選んだ $4$ 点の重みの和の最大値はいくつですか？

等脚台形を作ることができないときは -1 と出力してください。

なお、等脚台形とは以下の条件を全て満たす四角形のことです。

• 台形である
• 平行な $2$ つの辺のうち、$1$ つの辺の両端の角が等しい

制約

• $4 \\leq N \\leq 1000$
• $\-10^9 \\leq X_i,Y_i \\leq 10^9$
• $1 \\leq C_i \\leq 10^9$
• $i \\neq j$ ならば $(X_i,Y_i) \\neq (X_j,Y_j)$
• 入力は全て整数

入力

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

$N$ $X_1$ $Y_1$ $C_1$ $X_2$ $Y_2$ $C_2$ $\\vdots$ $X_N$ $Y_N$ $C_N$

出力

答えを出力せよ。

入力例 1

5
0 3 10
3 3 10
-1 0 10
2 0 10000
4 0 10

出力例 1

40

点 $1,2,3,5$ を選ぶことで等脚台形を作ることができ、点の重みの和は $40$ です。
それ以外の点の選び方では等脚台形を作ることはできません。

入力例 2

6
0 1 1
1 4 20
2 7 300
5 6 4000
4 3 50000
3 0 600000

出力例 2

650021

正方形や長方形も等脚台形に含まれることに注意してください。

入力例 3

7
-3 0 1
-2 0 1
-1 0 1
0 0 1
1 0 1
2 0 1
3 0 1

出力例 3

-1

等脚台形を作ることはできません。