题目描述

在 $xy$ 平面上，我们有 $N$ 个点，每个点都有一个权重。第 $i$ 个点的坐标为 $(X_i,Y_i)$，权重为 $C_i$。

我们将选择其中四个点，组成一个等腰梯形，梯形的顶点就是选择的四个点。在这些选择的点中，最大可能的总权重是多少？

如果无法组成等腰梯形，则输出 -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

我们无法组成等腰梯形。