El Reino de JOI es famoso por su producción de oro. En el Reino de JOI, una vez al año, se utiliza una excavadora para extraer oro.

El territorio del Reino de JOI se describe como un plano con coordenadas ~xy~. Hay ~N~ puntos en el terreno. El ~i-~ésimo punto (~1 \leq i \leq N~) es ~(X_i, Y_i)~. Cada punto contiene oro o roca, pero no ambos.

Si el punto ~i~ contiene oro, al extraerlo una vez, se obtiene oro de valor ~V_i~. Si el punto ~i~ contiene roca, al extraerlo una vez, se obtiene roca. El costo para desecharla es ~C_i~.

La extracción se realiza con una excavadora de la siguiente manera:

• Primero, se eligen dos líneas paralelas en el plano ~xy~.
• Luego, se extrae todo el oro y la roca, una vez de cada uno, en el área comprendida entre las dos líneas paralelas (incluyendo el oro o la roca que se encuentre sobre ellas).

La ganancia del Reino de JOI es el valor total del oro en el área de extracción menos el costo total de desechar las rocas en la misma área. Se quiere maximizar las ganancias del Reino JOI.

Escribe un programa que calcule la ganancia máxima del Reino JOI.

Entrada

La primera línea de entrada contiene un entero ~N~ (~1 \leq N \leq 2000~) ~-~ el número de espacios donde se puede extraer oro o roca.

La ~i-~ésima línea (~1 \leq i \leq N~) de las siguientes ~N~ líneas contiene tres enteros separados por espacios: ~X_i~, ~Y_i~, ~W_i~ (~-10^9 \leq X_i, Y_i \leq 10^9~, ~1 \leq |W_i| \leq 10^9~).

• Si ~W_i \geq 1~, el ~i-~ésimo espacio ~(X_i, Y_i)~ contiene oro. Al extraerlo una vez, obtenemos oro de valor ~V_i = W_i~.
• Si ~W_i \leq -1~, el ~i-~ésimo espacio ~(X_i, Y_i)~ contiene roca. Al extraerlo una vez, obtenemos roca, y el costo de desecharla es ~C_i = W_i~.

Se asegura que ~(X_i, Y_i) \neq (X_j, Y_j)~ para ~1 \leq i < j \leq N~ y que ~W_i \neq 0~.

Salida

La salida contiene la ganancia máxima del Reino JOI.

Subtareas

Subtarea	Puntos	Restricciones adicionales
~1~	~5~	~N \leq 100~, ~Y_i = 0~ para ~1 \le i \le N~.
~2~	~20~	~N \leq 100~. No hay tres puntos distintos sobre una línea. Sea ~L~ una línea en el plano ~xy~ que pasa por dos puntos distintos. Sea ~L'~ otra línea, distinta de ~L~, en el plano ~xy~ que pasa por dos puntos distintos. Entonces, ~L~ y ~L'~ no son paralelas entre sí.
~3~	~35~	No hay tres puntos distintos sobre una línea. Sea ~L~ una línea en el plano ~xy~ que pasa por dos puntos distintos. Sea ~L'~ otra línea, distinta de ~L~, en el plano ~xy~ que pasa por dos puntos distintos. Entonces, ~L~ y ~L'~ no son paralelas entre sí.
~4~	~20~	No hay tres puntos distintos sobre una línea
~5~	~20~	Sin restricciones adicionales

Ejemplos

Entrada 1

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

Salida 1

19

En este ejemplo, las posiciones de oro y roca en el Reino JOI son las siguientes:

Se puede tomar oro o roca en las posiciones ~2, 3, 4~ y ~5~. Entonces, la ganancia del Reino JOI es ~19~. Esta es la ganancia máxima del Reino JOI.

Entrada 2

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

Salida 2

15

En este ejemplo, los puntos ~1, 2~ y ~3~ están sobre una línea. Además, los puntos ~4, 5~ y ~6~ también están sobre una línea.

Entrada 3

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

Salida 3

5

En este ejemplo, no hay tres puntos distintos sobre una línea. Sea ~L~ una línea que pasa por los puntos ~1~ y ~2~, y sea ~L'~ una línea que pasa por los puntos ~3~ y ~4~. Entonces, ~L~ y ~L'~ son paralelas entre sí.

Entrada 4

2
0 0 -1
1 0 -1

Salida 4

0

Es posible elegir el área sin oro ni rocas. La ganancia máxima es 0.

Entrada 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

Salida 5

107