题目描述

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

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

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

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

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

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

在一个平面直角坐标系中，给出 $n$ 个点（$4 \le n \le 1000$），坐标为 $(X_i,Y_i)$，权值为 $C_i$（$-10^9 \le X_i,Y_i \le 10^9$，$1 \le C_i \le 10^9$），请从这 $n$ 个点中选出四个点，使得以这四个点能作为一个等腰梯形的顶点。求选中的点所能得到的最大权值和，若不存在能构成等腰梯形的情况，输出 -1。

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

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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