Królestwo JOI słynie z wydobycia złota. Raz w roku w Królestwie JOI używa się buldożera do wydobywania złota.

Teren Królestwa JOI opisujemy jako płaszczyznę ze współrzędnymi $xy$. Na tym terenie znajduje się $N$ punktów. Punkt o numerze $i$ ($1\le i\le N$) ma współrzędne $(X_i,Y_i)$. W każdym punkcie znajduje się albo złoto, albo skała, ale nie oba naraz.

Jeśli w punkcie $i$ znajduje się złoto, po jednokrotnym wydobyciu otrzymujemy złoto o wartości $V_i$. Jeśli w punkcie $i$ znajduje się skała, po jednokrotnym wydobyciu otrzymujemy skałę. Koszt jej usunięcia wynosi $C_i$.

Buldożera używamy do wydobycia w następujący sposób. Najpierw wybieramy dwie równoległe proste na płaszczyźnie $xy$. Następnie wydobywamy całe złoto i wszystkie skały z obszaru pomiędzy tymi prostymi, każde jednokrotnie (wliczając złoto i skały leżące na tych prostych).

Zysk Królestwa JOI to łączna wartość złota w obszarze wydobycia pomniejszona o łączny koszt usunięcia skał w tym samym obszarze. Chcemy zmaksymalizować zysk Królestwa JOI.

Zadanie

Napisz program obliczający maksymalny zysk Królestwa JOI.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz wejścia zawiera liczbę całkowitą $N$, oznaczającą liczbę punktów, w których można wydobyć złoto lub skałę.

• Wiersz o numerze $i$ ($1\le i\le N$) spośród kolejnych $N$ wierszy zawiera trzy liczby całkowite $X_i,Y_i,W_i$, oddzielone spacjami.

  • Jeśli $W_i\ge 1$, w punkcie o numerze $i$, $(X_i,Y_i)$, znajduje się złoto. Po jednokrotnym wydobyciu otrzymujemy złoto o wartości $V_i=W_i$.
  • Jeśli $W_i\le -1$, w punkcie o numerze $i$, $(X_i,Y_i)$, znajduje się skała. Po jednokrotnym wydobyciu otrzymujemy skałę, a koszt jej usunięcia wynosi $C_i=-W_i$.

Zachodzi $W_i\ne 0$.

Wyjście

Wypisz jeden wiersz na standardowe wyjście. Powinien on zawierać maksymalny zysk Królestwa JOI.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $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)\ne (X_j,Y_j)$ ($1\le i<j\le N$).

Podzadania

Jest 5 podzadań. Punktacja i dodatkowe ograniczenia każdego z nich są następujące:

Podzadanie 1 [5 punktów]

• $N\le 100$.
• $Y_i=0$ ($1\le i\le N$). Innymi słowy, wszystkie punkty leżą na osi $x$.

Podzadanie 2 [20 punktów]

• $N\le 100$.
• Żadne trzy różne punkty nie leżą na jednej prostej.
• Niech $L$ będzie prostą na płaszczyźnie $xy$ przechodzącą przez dwa różne punkty. Niech $L'$ będzie inną prostą, różną od $L$, na płaszczyźnie $xy$, przechodzącą przez dwa różne punkty. Wówczas $L$ i $L'$ nie są równoległe.

Podzadanie 3 [35 punktów]

• Żadne trzy różne punkty nie leżą na jednej prostej.
• Niech $L$ będzie prostą na płaszczyźnie $xy$ przechodzącą przez dwa różne punkty. Niech $L'$ będzie inną prostą, różną od $L$, na płaszczyźnie $xy$, przechodzącą przez dwa różne punkty. Wówczas $L$ i $L'$ nie są równoległe.

Podzadanie 4 [20 punktów]

• Żadne trzy różne punkty nie leżą na jednej prostej.

Podzadanie 5 [20 punktów]

Nie ma dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

19

Uwagi

W pierwszym przykładzie położenie złota i skał w Królestwie JOI jest następujące.

Złoto, skała.

W tym przykładzie możemy wydobyć złoto lub skały w punktach 2, 3, 4, 5. Zysk Królestwa JOI wynosi wtedy 19. Jest to maksymalny zysk Królestwa JOI.

Wejście 2

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

Wyjście 2

15

Uwagi

W drugim przykładzie punkty 1, 2, 3 leżą na jednej prostej. Również punkty 4, 5, 6 leżą na jednej prostej.

Wejście 3

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

Wyjście 3

5

Uwagi

W trzecim przykładzie żadne trzy różne punkty nie leżą na jednej prostej. Niech $L$ będzie prostą przechodzącą przez punkty 1 i 2, a $L'$ prostą przechodzącą przez punkty 3 i 4. Wówczas $L$ i $L'$ są równoległe.

Wejście 4

2
0 0 -1
1 0 -1

Wyjście 4

0

Uwagi

Można wybrać obszar bez złota i skał. W czwartym przykładzie maksymalny zysk wynosi 0.

Wejście 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

Wyjście 5

107