JOI патшалығы алтын өндірумен әйгілі. JOI патшалығында жылына бір рет алтын қазып алу үшін бульдозер қолданылады.

JOI патшалығының жері $xy$-координаталары бар жазықтық ретінде сипатталады. Жерде $N$ орын бар. $i$-ші орын ($1 \le i \le N$) $(X_i, Y_i)$ нүктесінде орналасқан. Әрбір орында не алтын, не тас бар, бірақ екеуі қатар болмайды.

Егер $i$ орнында алтын болса, оны бір рет қазып алғанда біз құндылығы $V_i$ болатын алтын аламыз. Егер $i$ орнында тас болса, оны бір рет қазып алғанда біз тас аламыз. Оны лақтырып тастау шығыны $C_i$-ге тең.

Біз қазба жұмыстары үшін бульдозерді келесідей қолданамыз. Алдымен $xy$-жазықтығында параллель екі түзу таңдаймыз. Содан кейін осы параллель екі түзудің арасындағы аймақтағы (түзулердің өз бойында жатқан алтын мен тасты қоса алғанда) барлық алтын мен тасты әрқайсысын бір реттен қазып аламыз.

JOI патшалығының пайдасы — қазу аймағындағы алтынның жалпы құндылығынан сол аймақтағы тасты лақтырып тастаудың жалпы шығынын азайтқанға тең. Біз JOI патшалығының пайдасын барынша арттырғымыз келеді.

Тапсырма

JOI патшалығының ең үлкен пайдасын есептейтін программа жазыңыз.

Кіріс деректер

Стандартты енгізу ағынынан келесі деректерді оқыңыз.

• Кіріс деректердің бірінші жолында алтын немесе тас алуға болатын орындар саны — $N$ бүтін саны берілген.

• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бос орынмен бөлінген үш бүтін сан $X_i, Y_i, W_i$ берілген.

  • Егер $W_i \ge 1$ болса, $i$-ші орында $(X_i, Y_i)$ алтын бар. Оны бір рет қазып алғанда, құндылығы $V_i = W_i$ болатын алтын аламыз.
  • Егер $W_i \le -1$ болса, $i$-ші орында $(X_i, Y_i)$ тас бар. Оны бір рет қазып алғанда, тас аламыз, ал оны лақтырып тастау шығыны $C_i = -W_i$ болады.

  $W_i \neq 0$ шарты орындалады.

Шығыс деректер

Стандартты шығару ағынына бір жол шығарыңыз. Шығыс деректерде JOI патшалығының ең үлкен пайдасы болуы тиіс.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады.

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

Ішкі есептер

Барлығы 5 ішкі есеп бар. Әрбір ішкі есептің ұпайы мен қосымша шектеулері төмендегідей:

Ішкі есеп 1 [5 ұпай]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). Басқаша айтқанда, барлық орындар $x$ осінің бойында жатыр.

Ішкі есеп 2 [20 ұпай]

• $N \le 100$.
• Ешқандай әртүрлі үш орын бір түзудің бойында жатпайды.
• $L$ — $xy$-жазықтығындағы әртүрлі екі орын арқылы өтетін түзу болсын. $L'$ — $xy$-жазықтығындағы әртүрлі екі орын арқылы өтетін, $L$-ден өзге екінші бір түзу болсын. Сонда $L$ мен $L'$ өзара параллель емес.

Ішкі есеп 3 [35 ұпай]

• Ешқандай әртүрлі үш орын бір түзудің бойында жатпайды.
• $L$ — $xy$-жазықтығындағы әртүрлі екі орын арқылы өтетін түзу болсын. $L'$ — $xy$-жазықтығындағы әртүрлі екі орын арқылы өтетін, $L$-ден өзге екінші бір түзу болсын. Сонда $L$ мен $L'$ өзара параллель емес.

Ішкі есеп 4 [20 ұпай]

• Ешқандай әртүрлі үш орын бір түзудің бойында жатпайды.

Ішкі есеп 5 [20 ұпай]

Қосымша шектеулер жоқ.

Мысалдар

Кіріс деректер 1

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

Шығыс деректер 1

19

Ескертпе

1-ші кіріс мысалында JOI патшалығындағы алтын (Gold) мен тастың (Rock) орналасуы төмендегідей.

Бұл кіріс мысалында біз $2, 3, 4, 5$ орындарындағы алтынды немесе тасты ала аламыз. Сонда JOI патшалығының пайдасы $19$ болады. Бұл — JOI патшалығының ең үлкен пайдасы.

Кіріс деректер 2

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

Шығыс деректер 2

15

Ескертпе

2-ші кіріс мысалында $1, 2, 3$ орындары бір түзудің бойында жатыр. Сонымен қатар, $4, 5, 6$ орындары да бір түзудің бойында жатыр.

Кіріс деректер 3

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

Шығыс деректер 3

5

Ескертпе

3-ші кіріс мысалында ешқандай әртүрлі үш орын бір түзудің бойында жатпайды. $L$ — $1$ және $2$ орындары арқылы өтетін түзу, ал $L'$ — $3$ және $4$ орындары арқылы өтетін түзу болсын. Сонда $L$ мен $L'$ өзара параллель болады.

Кіріс деректер 4

2
0 0 -1
1 0 -1

Шығыс деректер 4

0

Ескертпе

Ішінде ешқандай алтын да, тас та жоқ аймақты таңдауға болады. 4-ші кіріс мысалында ең үлкен пайда $0$-ге тең.

Кіріс деректер 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

Шығыс деректер 5

107