题目背景

如果你玩过 OI 教练模拟器，那么你应该知道 FJ 有很多台风...

题目描述

小 Z 的果园里有很多棵果树，但也有一些杂草。

对于第 $i$ 株植物来说，它位于平面上的点 $(x_i,y_i)$ 处，且它能为小 Z 带来 $w_i$ 的收益（有正有负，表示果树与杂草），保证没有三点共线。

为了抵御即将来临的台风，小 Z 决定建设一个凸多边形（不能退化为点或线段）的屏障，其中每个顶点必须是一棵植物。

定义一个屏障的收益等于其中（包括顶点）所有植物的收益之和。

请你求出，在所有可能的屏障中，最大的收益是多少。当然，小 Z 也可以不建屏障以获得 $0$ 的收益。

输入格式

第一行一个正整数 $n$，表示植物的数量。

接下来 $n$ 行，每行 $3$ 个整数 $x_i,y_i,w_i$，表示一棵植物的三个参数。

输出格式

一行一个整数，表示最大的收益。

样例 1 输入

4
1 1 1
1 2 1
2 1 1
2 2 -1

样例 1 输出

3

样例 2 输入

3
1 1 1
2 1 -1
2 2 -1

样例 2 输出

0

样例 3

见选手目录下的 $\boldsymbol{typhoon/typhoon3.in}$ 与 $\boldsymbol{typhoon/typhoon3.ans}$。

该样例满足子任务 $2$ 的限制。

样例 4

见选手目录下的 $\boldsymbol{typhoon/typhoon4.in}$ 与 $\boldsymbol{typhoon/typhoon4.ans}$。

该样例满足子任务 $4$ 的限制。

样例 5

见选手目录下的 $\boldsymbol{typhoon/typhoon5.in}$ 与 $\boldsymbol{typhoon/typhoon5.ans}$。

该样例满足子任务 $6$ 的限制。

样例 6

见选手目录下的 $\boldsymbol{typhoon/typhoon6.in}$ 与 $\boldsymbol{typhoon/typhoon6.ans}$。

该样例满足子任务 $9$ 的限制。

数据范围

本题使用子任务（Subtask）计分。你需要通过一个子任务内所有测试数据才可以获得相应的得分。

对于所有测试数据，保证：

• $1\le n\le300$；
• $-10^9\le x_i,y_i,w_i\le10^9$。

特殊性质 A：保证 $x_i=i$。

特殊性质 B：保证 $y_i=x_i^2$。

特殊性质 C：保证 $y_i<y_{i+1}$。

特殊性质 D：保证 $-1\le w_i\le 1$。