Kungariket JOI är berömt för att producera guld. I Kungariket JOI använder man en gång om året en schaktmaskin för att bryta guld.

Kungariket JOI:s mark beskrivs som ett plan med $xy$-koordinater. Det finns $N$ platser på marken. Den $i$-te platsen ($1 \le i \le N$) är $(X_i, Y_i)$. Varje plats har antingen guld eller sten, men inte båda.

Om plats $i$ har guld får vi, när vi bryter den en gång, guld av värde $V_i$. Om plats $i$ har sten får vi, när vi bryter den en gång, sten. Kostnaden för att göra sig av med den är $C_i$.

Vi använder en schaktmaskin för brytningen på följande sätt. Först väljer vi två parallella linjer i $xy$-planet. Därefter bryter vi allt guld och all sten, en gång vardera, i området mellan de två parallella linjerna (inklusive guld eller sten som ligger på själva linjerna).

Kungariket JOI:s vinst är det totala värdet av guldet i brytningsområdet minus den totala kostnaden för att göra sig av med stenen i samma område. Vi vill maximera Kungariket JOI:s vinst.

Uppgift

Skriv ett program som beräknar den maximala vinsten för Kungariket JOI.

Indata

Läs in följande data från standard inmatning.

• Den första raden i indata innehåller ett heltal $N$, antalet platser där vi kan ta guld eller sten.

• Den $i$-te raden ($1 \le i \le N$) av de följande $N$ raderna innehåller tre blankstegsseparerade heltal $X_i, Y_i, W_i$.

  • Om $W_i \ge 1$ har den $i$-te platsen $(X_i, Y_i)$ guld. När vi bryter den en gång får vi guld av värde $V_i = W_i$.
  • Om $W_i \le -1$ har den $i$-te platsen $(X_i, Y_i)$ sten. När vi bryter den en gång får vi sten, och kostnaden för att göra sig av med den är $C_i = -W_i$.

  Villkoret $W_i \neq 0$ är uppfyllt.

Utdata

Skriv ut en rad till standard utmatning. Utdata ska innehålla den maximala vinsten för Kungariket JOI.

Begränsningar

Alla indata uppfyller följande villkor.

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

Deluppgifter

Det finns 5 deluppgifter. Poängen och de ytterligare begränsningarna för varje deluppgift är följande:

Deluppgift 1 [5 poäng]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). Med andra ord ligger alla platser på $x$-axeln.

Deluppgift 2 [20 poäng]

• $N \le 100$.
• Inga tre skilda platser ligger på samma räta linje.
• Låt $L$ vara en linje i $xy$-planet som går genom två skilda platser. Låt $L'$ vara en annan linje i $xy$-planet, skild från $L$, som går genom två skilda platser. Då är $L$ och $L'$ inte parallella med varandra.

Deluppgift 3 [35 poäng]

• Inga tre skilda platser ligger på samma räta linje.
• Låt $L$ vara en linje i $xy$-planet som går genom två skilda platser. Låt $L'$ vara en annan linje i $xy$-planet, skild från $L$, som går genom två skilda platser. Då är $L$ och $L'$ inte parallella med varandra.

Deluppgift 4 [20 poäng]

• Inga tre skilda platser ligger på samma räta linje.

Deluppgift 5 [20 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

19

Förklaring

I exempelindata 1 är positionerna för guld (Gold) och sten (Rock) i Kungariket JOI följande.

I dessa exempelindata kan vi ta guld eller sten på platserna $2, 3, 4, 5$. Då blir Kungariket JOI:s vinst $19$. Detta är den maximala vinsten för Kungariket JOI.

Indata 2

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

Utdata 2

15

Förklaring

I exempelindata 2 ligger platserna $1, 2, 3$ på en linje. Dessutom ligger platserna $4, 5, 6$ på en linje.

Indata 3

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

Utdata 3

5

Förklaring

I exempelindata 3 ligger inga tre skilda platser på en linje. Låt $L$ vara en linje som går genom platserna $1$ och $2$, och låt $L'$ vara en linje som går genom platserna $3$ och $4$. Då är $L$ och $L'$ parallella med varandra.

Indata 4

2
0 0 -1
1 0 -1

Utdata 4

0

Förklaring

Det är möjligt att välja ett område utan något guld eller någon sten alls. I exempelindata 4 är den maximala vinsten $0$.

Indata 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

Utdata 5

107