Konungsríkið JOI er frægt fyrir gullframleiðslu. Í Konungsríkinu JOI nota menn jarðýtu einu sinni á ári til að vinna gull.

Landi Konungsríkisins JOI er lýst sem sléttu með $xy$-hnitum. Það eru $N$ staðir í landinu. $i$-ti staðurinn ($1 \le i \le N$) er $(X_i, Y_i)$. Á hverjum stað er annaðhvort gull eða grjót, en ekki hvort tveggja.

Ef gull er á stað $i$, þá fáum við gull að verðmæti $V_i$ þegar við vinnum hann einu sinni. Ef grjót er á stað $i$, þá fáum við grjót þegar við vinnum hann einu sinni. Kostnaðurinn við að losa sig við það er $C_i$.

Við notum jarðýtu við vinnsluna á eftirfarandi hátt. Fyrst veljum við tvær samsíða línur í $xy$-sléttunni. Síðan vinnum við allt gull og allt grjót, einu sinni á hverjum stað, á svæðinu á milli samsíða línanna tveggja (þar með talið gull eða grjót sem liggur á línunum sjálfum).

Hagnaður Konungsríkisins JOI er heildarverðmæti gullsins á vinnslusvæðinu að frádregnum heildarkostnaði við að losa sig við grjótið á sama svæði. Við viljum hámarka hagnað Konungsríkisins JOI.

Verkefni

Skrifið forrit sem reiknar mesta mögulega hagnað Konungsríkisins JOI.

Inntak

Lesið eftirfarandi gögn af staðalinntaki.

• Fyrsta lína inntaksins inniheldur heiltölu $N$, fjölda staða þar sem við getum tekið gull eða grjót.

• $i$-ta línan ($1 \le i \le N$) af næstu $N$ línum inniheldur þrjár heiltölur $X_i, Y_i, W_i$ aðskildar með bilum.

  • Ef $W_i \ge 1$, þá hefur $i$-ti staðurinn $(X_i, Y_i)$ gull. Þegar við vinnum hann einu sinni fáum við gull að verðmæti $V_i = W_i$.
  • Ef $W_i \le -1$, þá hefur $i$-ti staðurinn $(X_i, Y_i)$ grjót. Þegar við vinnum hann einu sinni fáum við grjót, og kostnaðurinn við að losa sig við það er $C_i = -W_i$.

  Skilyrðið $W_i \neq 0$ er uppfyllt.

Úttak

Skrifið eina línu á staðalúttak. Úttakið á að innihalda mesta mögulega hagnað Konungsríkisins JOI.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

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

Undirverkefni

Það eru 5 undirverkefni. Stigafjöldi og viðbótarskorður hvers undirverkefnis eru sem hér segir:

Undirverkefni 1 [5 stig]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). Með öðrum orðum liggja allir staðirnir á $x$-ásnum.

Undirverkefni 2 [20 stig]

• $N \le 100$.
• Engir þrír ólíkir staðir liggja á sömu línu.
• Látum $L$ vera línu í $xy$-sléttunni sem liggur í gegnum tvo ólíka staði. Látum $L'$ vera aðra línu í $xy$-sléttunni, ólíka $L$, sem liggur í gegnum tvo ólíka staði. Þá eru $L$ og $L'$ ekki samsíða hvor annarri.

Undirverkefni 3 [35 stig]

• Engir þrír ólíkir staðir liggja á sömu línu.
• Látum $L$ vera línu í $xy$-sléttunni sem liggur í gegnum tvo ólíka staði. Látum $L'$ vera aðra línu í $xy$-sléttunni, ólíka $L$, sem liggur í gegnum tvo ólíka staði. Þá eru $L$ og $L'$ ekki samsíða hvor annarri.

Undirverkefni 4 [20 stig]

• Engir þrír ólíkir staðir liggja á sömu línu.

Undirverkefni 5 [20 stig]

Engar viðbótarskorður eru til staðar.

Dæmi

Inntak 1

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

Úttak 1

19

Athugasemd

Í sýnidæmi 1 eru staðsetningar gulls (Gold) og grjóts (Rock) í Konungsríkinu JOI sem hér segir.

Í þessu sýnidæmi getum við tekið gull eða grjót á stöðum $2, 3, 4, 5$. Þá er hagnaður Konungsríkisins JOI jafn $19$. Þetta er mesti mögulegi hagnaður Konungsríkisins JOI.

Inntak 2

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

Úttak 2

15

Athugasemd

Í sýnidæmi 2 liggja staðir $1, 2, 3$ á einni línu. Auk þess liggja staðir $4, 5, 6$ á einni línu.

Inntak 3

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

Úttak 3

5

Athugasemd

Í sýnidæmi 3 liggja engir þrír ólíkir staðir á sömu línu. Látum $L$ vera línu sem liggur í gegnum staði $1$ og $2$, og látum $L'$ vera línu sem liggur í gegnum staði $3$ og $4$. Þá eru $L$ og $L'$ samsíða hvor annarri.

Inntak 4

2
0 0 -1
1 0 -1

Úttak 4

0

Athugasemd

Mögulegt er að velja svæði án nokkurs gulls eða grjóts. Í sýnidæmi 4 er mesti mögulegi hagnaðurinn $0$.

Inntak 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

Úttak 5

107