Byteasar 刚刚买了一块农田。他的田里有 $n$ 株植物，每株植物都有一定的年产量。产量可以是正数（例如果树），也可以是负数（例如常见的害虫，它们只会消耗土壤、阳光、水和养分，而这些资源本可以被其他植物更好地利用）。

Byteasar 估算了每株植物的年产量。由于严格的环保法律，Byteasar 不能简单地移除产量为负的植物。既然他无论如何都要给他的田地围上栅栏，他打算只圈起那部分能使总年产量最大化的区域——虽然他无法摆脱害虫，但他绝对不会在保护它们上投入时间和金钱！

Byteasar 请求你帮助他优化栅栏的布局。栅栏的建造方式很节俭：Byteasar 将选择田里植物的一个子集，并利用这些植物作为支撑点来架设铁丝网围栏。因此，被围起来的区域必须是一个面积为正的凸多边形。请帮助 Byteasar 选择作为栅栏顶点（即支撑点）的植物，使得被围在栅栏内的植物的总产量最大化。

输入格式

输入的第一行包含一个整数 $n$ ($n \ge 3$)，表示 Byteasar 田里的植物数量。 接下来的 $n$ 行描述了这些植物：第 $i$ 行包含三个整数 $x_i, y_i$ 和 $v_i$ ($-10^9 \le x_i, y_i \le 10^9, -10^9 \le v_i \le 10^9$)，分别表示第 $i$ 株植物在笛卡尔坐标系中的坐标 $(x_i, y_i)$，以及该植物的产量 $v_i$（正数代表果树，负数代表害虫）。保证任意三点不共线。

输出格式

输出一行，包含栅栏所能围住的植物的最大总产量。

样例

样例输入 1

6
0 0 1
0 4 1
4 0 1
4 4 1
1 2 -1
2 6 -5

样例输出 1

3

说明 1

下图展示了一个最优的栅栏布局，其总产量为 3。另一种获得相同产量的方法是选择点 $(0, 0), (4, 0)$ 和 $(4, 4)$ 作为栅栏的顶点。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试点。