Das Königreich JOI ist für seine Goldgewinnung bekannt. Einmal im Jahr wird dort mit einem Bulldozer Gold abgebaut.

Das Gebiet des Königreichs JOI wird als Ebene mit $xy$-Koordinaten beschrieben. In diesem Gebiet gibt es $N$ Fundstellen. Die $i$-te Fundstelle ($1 \le i \le N$) liegt bei $(X_i,Y_i)$. Jede Fundstelle enthält entweder Gold oder Gestein, aber nicht beides.

Enthält die Fundstelle $i$ Gold, so erhalten wir beim einmaligen Abbau Gold im Wert von $V_i$. Enthält die Fundstelle $i$ Gestein, so erhalten wir beim einmaligen Abbau Gestein. Die Kosten für dessen Entsorgung betragen $C_i$.

Wir verwenden den Bulldozer wie folgt zum Abbau. Zunächst wählen wir zwei parallele Geraden in der $xy$-Ebene. Dann bauen wir im Bereich zwischen diesen beiden parallelen Geraden sämtliches Gold und Gestein jeweils einmal ab (einschließlich des Goldes und Gesteins, das auf den Geraden liegt).

Der Gewinn des Königreichs JOI ist der Gesamtwert des Goldes im Abbaugebiet abzüglich der Gesamtkosten für die Entsorgung des Gesteins im selben Gebiet. Wir möchten den Gewinn des Königreichs JOI maximieren.

Aufgabe

Schreibe ein Programm, das den maximalen Gewinn des Königreichs JOI berechnet.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

• Die erste Eingabezeile enthält eine ganze Zahl $N$, die Anzahl der Fundstellen, an denen Gold oder Gestein abgebaut werden kann.

• Die $i$-te Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen enthält drei durch Leerzeichen getrennte ganze Zahlen $X_i$, $Y_i$, $W_i$.

  • Falls $W_i \ge 1$, enthält die $i$-te Fundstelle $(X_i,Y_i)$ Gold. Beim einmaligen Abbau erhalten wir Gold im Wert von $V_i=W_i$.
  • Falls $W_i \le -1$, enthält die $i$-te Fundstelle $(X_i,Y_i)$ Gestein. Beim einmaligen Abbau erhalten wir Gestein, dessen Entsorgungskosten $C_i=-W_i$ betragen.

  Es gilt $W_i \ne 0$.

Ausgabe

Gib eine Zeile auf der Standardausgabe aus. Die Ausgabe enthält den maximalen Gewinn des Königreichs JOI.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Es gibt 5 Teilaufgaben. Die Punktzahlen und zusätzlichen Beschränkungen der einzelnen Teilaufgaben sind wie folgt:

Teilaufgabe 1 [5 Punkte]

• $N \le 100$.
• $Y_i=0$ ($1 \le i \le N$). Mit anderen Worten liegen alle Fundstellen auf der $x$-Achse.

Teilaufgabe 2 [20 Punkte]

• $N \le 100$.
• Keine drei verschiedenen Fundstellen liegen auf einer Geraden.
• Sei $L$ eine Gerade in der $xy$-Ebene, die durch zwei verschiedene Fundstellen verläuft. Sei $L'$ eine andere, von $L$ verschiedene Gerade in der $xy$-Ebene, die durch zwei verschiedene Fundstellen verläuft. Dann sind $L$ und $L'$ nicht parallel zueinander.

Teilaufgabe 3 [35 Punkte]

• Keine drei verschiedenen Fundstellen liegen auf einer Geraden.
• Sei $L$ eine Gerade in der $xy$-Ebene, die durch zwei verschiedene Fundstellen verläuft. Sei $L'$ eine andere, von $L$ verschiedene Gerade in der $xy$-Ebene, die durch zwei verschiedene Fundstellen verläuft. Dann sind $L$ und $L'$ nicht parallel zueinander.

Teilaufgabe 4 [20 Punkte]

• Keine drei verschiedenen Fundstellen liegen auf einer Geraden.

Teilaufgabe 5 [20 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

19

Hinweis

In Beispieleingabe 1 befinden sich Gold und Gestein im Königreich JOI an den folgenden Positionen.

Gold: Gold; Rock: Gestein.

In dieser Beispieleingabe können wir an den Fundstellen $2$, $3$, $4$, $5$ Gold oder Gestein abbauen. Dann beträgt der Gewinn des Königreichs JOI $19$. Dies ist der maximale Gewinn des Königreichs JOI.

Eingabe 2

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

Ausgabe 2

15

Hinweis

In Beispieleingabe 2 liegen die Fundstellen $1$, $2$, $3$ auf einer Geraden. Auch die Fundstellen $4$, $5$, $6$ liegen auf einer Geraden.

Eingabe 3

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

Ausgabe 3

5

Hinweis

In Beispieleingabe 3 liegen keine drei verschiedenen Fundstellen auf einer Geraden. Sei $L$ die Gerade durch die Fundstellen $1$ und $2$ und $L'$ die Gerade durch die Fundstellen $3$ und $4$. Dann sind $L$ und $L'$ parallel zueinander.

Eingabe 4

2
0 0 -1
1 0 -1

Ausgabe 4

0

Hinweis

Es ist möglich, ein Gebiet ohne Gold und Gestein zu wählen. In Beispieleingabe 4 beträgt der maximale Gewinn $0$.

Eingabe 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

Ausgabe 5

107