I.

中文名：做出最棒的蛋糕
时间限制：2 秒
难度评估：CF 2600
题型标签：计算几何、凸集、最大权闭包思想、动态规划

题目描述

Japan Alumni Group 将举行派对。你为派对买了一个蛋糕。

蛋糕可以看作二维平面上的一个巨大正方形，四个顶点分别为

$$(-10^{100},-10^{100}), (10^{100},-10^{100}), (10^{100},10^{100}), (-10^{100},10^{100})。$$

蛋糕上有若干草莓，每个草莓可以看作平面上的一个点，并且每个草莓有一个整数美味值。

派对参加者都很喜欢草莓，因此他们认为蛋糕的美味程度等于蛋糕上所有草莓美味值的总和。

你想让最终端上桌的蛋糕美味值最大。但是如果直接移除草莓，会留下痕迹，不好看。因此你决定执行下面的操作任意多次，也可以不执行：

• 选择一条直线，沿这条直线把蛋糕切成两部分，并丢弃其中一部分。

但有两个限制：

• 不能选择经过某个草莓的直线；
• 不能选择不穿过蛋糕严格内部的直线。

请计算经过若干次操作后，蛋糕上草莓美味值之和可能达到的最大值。

输入格式

输入只有一个数据集：

n
x_1 y_1 w_1
x_2 y_2 w_2
...
x_n y_n w_n

其中：

• $1\le n\le 300$；
• $-100000\le x_i,y_i\le 100000$；
• $-10^9\le w_i\le 10^9$；
• 任意两个草莓坐标不同。

输出格式

输出操作后蛋糕上草莓美味值总和的最大可能值。

样例输入 1

5
0 0 5
10 0 10
5 5 -1
0 10 20
10 10 -10

样例输出 1

34

样例输入 2

5
1 1 -5
3 3 10
5 5 -4
7 7 7
9 9 -2

样例输出 2

13

样例输入 3

1
0 0 -100

样例输出 3

0