等腰梯形

题目描述

在 $xy$ 平面上有 $N$ 个点，每个点都被赋予一个权值。

第 $i$ 个点的坐标为 $(X_i,Y_i)$，权值为 $C_i$。

我们将从这 $N$ 个点中选择四个点，使得这四个点构成一个等腰梯形。

求所选点的权值总和的最大可能值。

如果无法构成等腰梯形，输出 -1。

提醒：等腰梯形是满足以下所有条件的四边形：

• 它是一个梯形。
• 对于两条平行边中的一条，其两端处的两个角相等。

输入格式

输入按以下格式从标准输入给出：

$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

无法构成等腰梯形。

数据范围

• $4 \le N \le 1000$
• $-10^9 \le X_i,Y_i \le 10^9$
• $1 \le C_i \le 10^9$
• 若 $i \neq j$，则 $(X_i,Y_i) \neq (X_j,Y_j)$
• 输入均为整数