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 的黃金與岩石位置如下。

Gold：黃金；Rock：岩石。

在此範例輸入中，我們可以取得地點 $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