JOI-kuningaskunta on kuuluisa kullan tuotannostaan. JOI-kuningaskunnassa käytetään kerran vuodessa puskutraktoria kullan louhimiseen.

JOI-kuningaskunnan maa kuvataan tasona, jossa on $xy$-koordinaatit. Maassa on $N$ esiintymää. $i$:s esiintymä ($1 \le i \le N$) on pisteessä $(X_i, Y_i)$. Jokaisessa esiintymässä on joko kultaa tai kiveä, mutta ei molempia.

Jos esiintymässä $i$ on kultaa, kun louhimme sen kerran, saamme kultaa, jonka arvo on $V_i$. Jos esiintymässä $i$ on kiveä, kun louhimme sen kerran, saamme kiveä. Sen hävittämisen kustannus on $C_i$.

Käytämme puskutraktoria louhintaan seuraavalla tavalla. Ensin valitsemme $xy$-tasosta kaksi yhdensuuntaista suoraa. Sitten louhimme kaiken kullan ja kiven, kunkin kerran, näiden kahden yhdensuuntaisen suoran väliseltä alueelta (mukaan lukien suorilla sijaitseva kulta tai kivi).

JOI-kuningaskunnan voitto on louhinta-alueen kullan kokonaisarvo vähennettynä saman alueen kivien hävittämisen kokonaiskustannuksella. Haluamme maksimoida JOI-kuningaskunnan voiton.

Tehtävä

Kirjoita ohjelma, joka laskee JOI-kuningaskunnan suurimman mahdollisen voiton.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• Syötteen ensimmäinen rivi sisältää kokonaisluvun $N$, niiden esiintymien lukumäärän, joista voimme ottaa kultaa tai kiveä.

• Seuraavien $N$ rivin $i$:s rivi ($1 \le i \le N$) sisältää kolme välilyönnein erotettua kokonaislukua $X_i, Y_i, W_i$.

  • Jos $W_i \ge 1$, $i$:nnessä esiintymässä $(X_i, Y_i)$ on kultaa. Kun louhimme sen kerran, saamme kultaa, jonka arvo on $V_i = W_i$.
  • Jos $W_i \le -1$, $i$:nnessä esiintymässä $(X_i, Y_i)$ on kiveä. Kun louhimme sen kerran, saamme kiveä, ja sen hävittämisen kustannus on $C_i = -W_i$.

  Ehto $W_i \neq 0$ pätee.

Tuloste

Kirjoita vakiotulosteeseen yksi rivi. Tulosteen tulee sisältää JOI-kuningaskunnan suurin mahdollinen voitto.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

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

Osatehtävät

Tehtävässä on 5 osatehtävää. Kunkin osatehtävän pistemäärä ja lisärajoitukset ovat seuraavat:

Osatehtävä 1 [5 pistettä]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). Toisin sanoen kaikki esiintymät sijaitsevat $x$-akselilla.

Osatehtävä 2 [20 pistettä]

• $N \le 100$.
• Mitkään kolme eri esiintymää eivät sijaitse samalla suoralla.
• Olkoon $L$ kahden eri esiintymän kautta kulkeva suora $xy$-tasossa. Olkoon $L'$ toinen, suorasta $L$ poikkeava kahden eri esiintymän kautta kulkeva suora $xy$-tasossa. Tällöin $L$ ja $L'$ eivät ole yhdensuuntaisia.

Osatehtävä 3 [35 pistettä]

• Mitkään kolme eri esiintymää eivät sijaitse samalla suoralla.
• Olkoon $L$ kahden eri esiintymän kautta kulkeva suora $xy$-tasossa. Olkoon $L'$ toinen, suorasta $L$ poikkeava kahden eri esiintymän kautta kulkeva suora $xy$-tasossa. Tällöin $L$ ja $L'$ eivät ole yhdensuuntaisia.

Osatehtävä 4 [20 pistettä]

• Mitkään kolme eri esiintymää eivät sijaitse samalla suoralla.

Osatehtävä 5 [20 pistettä]

Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

19

Huomautus

Esimerkkisyötteessä 1 kullan (Gold) ja kiven (Rock) sijainnit JOI-kuningaskunnassa ovat seuraavat.

Tässä esimerkkisyötteessä voimme ottaa kullan tai kiven esiintymistä $2, 3, 4, 5$. Tällöin JOI-kuningaskunnan voitto on $19$. Tämä on JOI-kuningaskunnan suurin mahdollinen voitto.

Syöte 2

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

Tuloste 2

15

Huomautus

Esimerkkisyötteessä 2 esiintymät $1, 2, 3$ sijaitsevat samalla suoralla. Myös esiintymät $4, 5, 6$ sijaitsevat samalla suoralla.

Syöte 3

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

Tuloste 3

5

Huomautus

Esimerkkisyötteessä 3 mitkään kolme eri esiintymää eivät sijaitse samalla suoralla. Olkoon $L$ esiintymien $1$ ja $2$ kautta kulkeva suora ja $L'$ esiintymien $3$ ja $4$ kautta kulkeva suora. Tällöin $L$ ja $L'$ ovat yhdensuuntaisia.

Syöte 4

2
0 0 -1
1 0 -1

Tuloste 4

0

Huomautus

On mahdollista valita alue, jolla ei ole lainkaan kultaa eikä kiveä. Esimerkkisyötteessä 4 suurin mahdollinen voitto on $0$.

Syöte 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

Tuloste 5

107