JOI 王国以盛产黄金而闻名。在 JOI 王国，每年都会使用推土机来开采黄金。

JOI 王国的土地被描述为一个具有 $xy$ 坐标的平面。土地上有 $N$ 个点。第 $i$ 个点 ($1 \le i \le N$) 的坐标为 $(X_i, Y_i)$。每个点要么有黄金，要么有岩石，二者必居其一。

如果点 $i$ 有黄金，开采一次可获得价值为 $V_i$ 的黄金。如果点 $i$ 有岩石，开采一次可获得岩石，但需要支付清理成本 $C_i$。

我们使用推土机进行开采的方式如下：首先，在 $xy$ 平面上选择两条平行线。然后，开采两条平行线区域内（包括位于线上的点）的所有黄金和岩石，每个点仅开采一次。

JOI 王国的利润等于开采区域内所有黄金的总价值减去开采区域内所有岩石的总清理成本。我们希望最大化 JOI 王国的利润。

题目描述

编写一个程序，计算 JOI 王国的最大利润。

输入格式

从标准输入读取以下数据。

• 第一行包含一个整数 $N$，表示可以获取黄金或岩石的点数。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含三个空格分隔的整数 $X_i, Y_i, W_i$。
  • 如果 $W_i \ge 1$，则第 $i$ 个点 $(X_i, Y_i)$ 有黄金。开采一次可获得价值 $V_i = W_i$ 的黄金。
  • 如果 $W_i \le -1$，则第 $i$ 个点 $(X_i, Y_i)$ 有岩石。开采一次可获得岩石，清理成本为 $C_i = -W_i$。
  • 满足 $W_i \neq 0$。

输出格式

向标准输出打印一行。输出包含 JOI 王国的最大利润。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 2\,000$。
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$)。
• $-1\,000\,000\,000 \le Y_i \le 1\,000\,000\,000$ ($1 \le i \le N$)。
• $1 \le |W_i| \le 1\,000\,000\,000$。
• $(X_i, Y_i) \neq (X_j, Y_j)$ ($1 \le i < j \le N$)。

子任务

共有 5 个子任务。各子任务的分数和附加限制如下：

子任务 1 [5 分] $N \le 100$。 $Y_i = 0$ ($1 \le i \le N$)。换句话说，所有点都在 $x$ 轴上。

子任务 2 [20 分] $N \le 100$。 没有三个不同的点在同一条直线上。 * 设 $L$ 为 $xy$ 平面上通过两个不同点的直线。设 $L'$ 为 $xy$ 平面上通过另外两个不同点的另一条直线，且 $L' \neq L$。则 $L$ 和 $L'$ 不平行。

子任务 3 [35 分] 没有三个不同的点在同一条直线上。 设 $L$ 为 $xy$ 平面上通过两个不同点的直线。设 $L'$ 为 $xy$ 平面上通过另外两个不同点的另一条直线，且 $L' \neq L$。则 $L$ 和 $L'$ 不平行。

子任务 4 [20 分] * 没有三个不同的点在同一条直线上。

子任务 5 [20 分] * 没有附加限制。

样例

样例输入 1

5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7

样例输出 1

19

样例输入 2

6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2

样例输出 2

15

样例输入 3

5
0 0 2
4 0 2
3 2 -1
1 2 2
1 1 -1

样例输出 3

5

样例输入 4

2
0 0 -1
1 0 -1

样例输出 4

0

样例输入 5

15
10 3 30
5 10 -17
4 -5 14
0 -3 -9
-2 3 17
6 9 -19
-9 -6 -14
-2 -3 10
-3 -3 30
8 1 -28
9 -9 -5
7 -5 -24
-8 -10 5
-7 2 20
10 -3 -13

样例输出 5

107

说明

在样例 1 中，我们可以选择点 2, 3, 4, 5 进行开采，此时 JOI 王国的利润为 19，这是最大利润。

在样例 2 中，点 1, 2, 3 在同一条直线上，点 4, 5, 6 也在同一条直线上。

在样例 3 中，没有三个不同的点在同一条直线上。设 $L$ 为通过点 1 和点 2 的直线，$L'$ 为通过点 3 和点 4 的直线，则 $L$ 和 $L'$ 平行。

在样例 4 中，可以选择不包含任何黄金或岩石的区域，此时最大利润为 0。