Il Regno JOI è famoso per la produzione di oro. Nel Regno JOI, una volta all'anno, si utilizza un bulldozer per estrarre l'oro.

Il territorio del Regno JOI è descritto come un piano con coordinate $xy$. Ci sono $N$ punti nel territorio. L'$i$-esimo punto ($1 \le i \le N$) è $(X_i, Y_i)$. In ogni punto si trova oro oppure roccia, ma non entrambi.

Se nel punto $i$ c'è oro, quando lo scaviamo una volta otteniamo oro di valore $V_i$. Se nel punto $i$ c'è roccia, quando lo scaviamo una volta otteniamo roccia. Il costo per smaltirla è $C_i$.

Usiamo un bulldozer per l'estrazione nel modo seguente. Prima scegliamo due rette parallele nel piano $xy$. Poi estraiamo tutto l'oro e tutta la roccia, una volta per ciascun punto, nell'area compresa tra le due rette parallele (inclusi l'oro o la roccia che giacciono su di esse).

Il profitto del Regno JOI è il valore totale dell'oro nell'area di estrazione meno il costo totale per smaltire la roccia nella stessa area. Vogliamo massimizzare il profitto del Regno JOI.

Compito

Scrivi un programma che calcoli il profitto massimo del Regno JOI.

Input

Leggi i seguenti dati dallo standard input.

• La prima riga dell'input contiene un intero $N$, il numero di punti in cui possiamo prelevare oro o roccia.

• La $i$-esima riga ($1 \le i \le N$) delle successive $N$ righe contiene tre interi separati da spazi $X_i, Y_i, W_i$.

  • Se $W_i \ge 1$, l'$i$-esimo punto $(X_i, Y_i)$ contiene oro. Quando lo scaviamo una volta, otteniamo oro di valore $V_i = W_i$.
  • Se $W_i \le -1$, l'$i$-esimo punto $(X_i, Y_i)$ contiene roccia. Quando lo scaviamo una volta, otteniamo roccia, e il costo per smaltirla è $C_i = -W_i$.

  Vale $W_i \neq 0$.

Output

Scrivi una riga sullo standard output. L'output deve contenere il profitto massimo del Regno JOI.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni.

• $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$).

Sottoproblemi

Ci sono 5 sottoproblemi. Il punteggio e i vincoli aggiuntivi di ciascun sottoproblema sono i seguenti:

Sottoproblema 1 [5 punti]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). In altre parole, tutti i punti giacciono sull'asse $x$.

Sottoproblema 2 [20 punti]

• $N \le 100$.
• Non ci sono tre punti distinti allineati su una stessa retta.
• Sia $L$ una retta nel piano $xy$ passante per due punti distinti. Sia $L'$ un'altra retta nel piano $xy$, diversa da $L$, passante per due punti distinti. Allora $L$ e $L'$ non sono parallele tra loro.

Sottoproblema 3 [35 punti]

• Non ci sono tre punti distinti allineati su una stessa retta.
• Sia $L$ una retta nel piano $xy$ passante per due punti distinti. Sia $L'$ un'altra retta nel piano $xy$, diversa da $L$, passante per due punti distinti. Allora $L$ e $L'$ non sono parallele tra loro.

Sottoproblema 4 [20 punti]

• Non ci sono tre punti distinti allineati su una stessa retta.

Sottoproblema 5 [20 punti]

Non ci sono vincoli aggiuntivi.

Esempi

Input 1

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

Output 1

19

Spiegazione

Nell'Input di esempio 1, le posizioni dell'oro (Gold) e della roccia (Rock) nel Regno JOI sono le seguenti.

In questo input di esempio, possiamo prelevare l'oro o la roccia nei punti $2, 3, 4, 5$. Allora il profitto del Regno JOI è $19$. Questo è il profitto massimo del Regno JOI.

Input 2

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

Output 2

15

Spiegazione

Nell'Input di esempio 2, i punti $1, 2, 3$ giacciono su una stessa retta. Inoltre, anche i punti $4, 5, 6$ giacciono su una stessa retta.

Input 3

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

Output 3

5

Spiegazione

Nell'Input di esempio 3, non ci sono tre punti distinti su una stessa retta. Sia $L$ la retta passante per i punti $1$ e $2$, e sia $L'$ la retta passante per i punti $3$ e $4$. Allora $L$ e $L'$ sono parallele tra loro.

Input 4

2
0 0 -1
1 0 -1

Output 4

0

Spiegazione

È possibile scegliere un'area senza oro né roccia. Nell'Input di esempio 4, il profitto massimo è $0$.

Input 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

Output 5

107