JOI Kingdom 以出產黃金聞名。喺 JOI Kingdom，每年都會用推土機採金一次。

JOI Kingdom 嘅土地可以用一個 $xy$ 座標平面描述。土地上有 $N$ 個地點，第 $i$ 個地點（$1 \le i \le N$）嘅座標係 $(X_i,Y_i)$。每個地點都有黃金或者岩石，但唔會兩樣都有。

如果第 $i$ 個地點有黃金，開採一次就可以得到價值 $V_i$ 嘅黃金。如果第 $i$ 個地點有岩石，開採一次就會得到岩石，而棄置呢啲岩石嘅成本係 $C_i$。

我哋會用以下方式操作推土機開採。首先，喺 $xy$ 平面上揀兩條平行直線。然後，開採兩條平行直線之間區域內所有黃金同岩石，每份只開採一次（亦包括喺兩條直線上嘅黃金同岩石）。

JOI Kingdom 嘅利潤，係開採區域內黃金嘅總價值，減去同一區域內棄置岩石嘅總成本。我哋想令 JOI Kingdom 嘅利潤最大。

任務

請寫一個程式，計算 JOI Kingdom 嘅最大利潤。

輸入格式

由標準輸入讀取以下資料。

• 第一行包含一個整數 $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 \ne 0$。

輸出格式

向標準輸出寫一行，內容係 JOI Kingdom 嘅最大利潤。

數據範圍

所有輸入資料都符合以下條件。

• $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) \ne (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$ 嘅直線。咁 $L$ 同 $L'$ 唔會互相平行。

子任務 3［35 分］

• 冇任何三個唔同嘅地點喺同一條直線上。
• 設 $L$ 係 $xy$ 平面上一條經過兩個唔同地點嘅直線，$L'$ 係 $xy$ 平面上另一條經過兩個唔同地點、而且唔同於 $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

說明

喺樣例輸入 1，JOI Kingdom 嘅黃金同岩石位置如下。

喺呢個樣例輸入，我哋可以開採第 $2,3,4,5$ 個地點嘅黃金或者岩石。咁 JOI Kingdom 嘅利潤就係 $19$。呢個就係 JOI Kingdom 嘅最大利潤。

輸入格式 2

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

輸出格式 2

15

說明

喺樣例輸入 2，第 $1,2,3$ 個地點喺同一條直線上，而第 $4,5,6$ 個地點亦喺同一條直線上。

輸入格式 3

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

輸出格式 3

5

說明

喺樣例輸入 3，冇任何三個唔同嘅地點喺同一條直線上。設 $L$ 係經過第 $1$ 同第 $2$ 個地點嘅直線，$L'$ 係經過第 $3$ 同第 $4$ 個地點嘅直線，咁 $L$ 同 $L'$ 就互相平行。

輸入格式 4

2
0 0 -1
1 0 -1

輸出格式 4

0

說明

可以揀一個冇任何黃金或者岩石嘅區域。喺樣例輸入 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