Kongeriket JOI er berømt for å produsere gull. I Kongeriket JOI bruker de én gang i året en bulldoser til å utvinne gull.

Landet i Kongeriket JOI beskrives som et plan med $xy$-koordinater. Det er $N$ steder i landet. Det $i$-te stedet ($1 \le i \le N$) er $(X_i, Y_i)$. Hvert sted har enten gull eller stein, men ikke begge deler.

Hvis sted $i$ har gull, får vi gull med verdi $V_i$ når vi utvinner det én gang. Hvis sted $i$ har stein, får vi stein når vi utvinner det én gang. Kostnaden for å kvitte seg med den er $C_i$.

Vi bruker en bulldoser til utvinning på følgende måte. Først velger vi to parallelle linjer i $xy$-planet. Deretter utvinner vi alt gull og all stein, én gang for hvert sted, i området mellom de to parallelle linjene (inkludert gull eller stein som ligger på selve linjene).

Fortjenesten til Kongeriket JOI er den totale verdien av gullet i utvinningsområdet minus den totale kostnaden for å kvitte seg med steinen i det samme området. Vi ønsker å maksimere fortjenesten til Kongeriket JOI.

Oppgave

Skriv et program som beregner den maksimale fortjenesten til Kongeriket JOI.

Inndata

Les følgende data fra standard inndata.

• Den første linjen i inndataene inneholder et heltall $N$, antallet steder der vi kan ta gull eller stein.

• Den $i$-te linjen ($1 \le i \le N$) av de neste $N$ linjene inneholder tre mellomromseparerte heltall $X_i, Y_i, W_i$.

  • Hvis $W_i \ge 1$, har det $i$-te stedet $(X_i, Y_i)$ gull. Når vi utvinner det én gang, får vi gull med verdi $V_i = W_i$.
  • Hvis $W_i \le -1$, har det $i$-te stedet $(X_i, Y_i)$ stein. Når vi utvinner det én gang, får vi stein, og kostnaden for å kvitte seg med den er $C_i = -W_i$.

  $W_i \neq 0$ er oppfylt.

Utdata

Skriv én linje til standard utdata. Utdataene skal inneholde den maksimale fortjenesten til Kongeriket JOI.

Begrensninger

Alle inndata oppfyller følgende betingelser.

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

Deloppgaver

Det er 5 deloppgaver. Poengsummen og tilleggsbegrensningene for hver deloppgave er som følger:

Deloppgave 1 [5 poeng]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). Med andre ord ligger alle stedene på $x$-aksen.

Deloppgave 2 [20 poeng]

• $N \le 100$.
• Ingen tre forskjellige steder ligger på samme linje.
• La $L$ være en linje i $xy$-planet som går gjennom to forskjellige steder. La $L'$ være en annen linje i $xy$-planet, forskjellig fra $L$, som går gjennom to forskjellige steder. Da er $L$ og $L'$ ikke parallelle med hverandre.

Deloppgave 3 [35 poeng]

• Ingen tre forskjellige steder ligger på samme linje.
• La $L$ være en linje i $xy$-planet som går gjennom to forskjellige steder. La $L'$ være en annen linje i $xy$-planet, forskjellig fra $L$, som går gjennom to forskjellige steder. Da er $L$ og $L'$ ikke parallelle med hverandre.

Deloppgave 4 [20 poeng]

• Ingen tre forskjellige steder ligger på samme linje.

Deloppgave 5 [20 poeng]

Det er ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

19

Merknad

I eksempelinndata 1 er posisjonene til gull (Gold) og stein (Rock) i Kongeriket JOI som følger.

I disse eksempelinndataene kan vi ta gull eller stein på stedene $2, 3, 4, 5$. Da blir fortjenesten til Kongeriket JOI lik $19$. Dette er den maksimale fortjenesten til Kongeriket JOI.

Inndata 2

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

Utdata 2

15

Merknad

I eksempelinndata 2 ligger stedene $1, 2, 3$ på én linje. I tillegg ligger stedene $4, 5, 6$ på én linje.

Inndata 3

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

Utdata 3

5

Merknad

I eksempelinndata 3 ligger ingen tre forskjellige steder på samme linje. La $L$ være en linje som går gjennom stedene $1$ og $2$, og la $L'$ være en linje som går gjennom stedene $3$ og $4$. Da er $L$ og $L'$ parallelle med hverandre.

Inndata 4

2
0 0 -1
1 0 -1

Utdata 4

0

Merknad

Det er mulig å velge et område uten gull eller stein. I eksempelinndata 4 er den maksimale fortjenesten $0$.

Inndata 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