配点 : $600$ 点

問題文

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

出力

答えを出力せよ。

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

40

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

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

650021

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

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

-1

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