JOI Kingdom es famoso por producir oro. En JOI Kingdom, una vez al año se utiliza una excavadora para extraer oro.

El territorio de JOI Kingdom se describe como un plano con coordenadas $xy$. Hay $N$ puntos en el territorio. El punto $i$ ($1 \le i \le 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 obtenemos oro de valor $V_i$. Si el punto $i$ contiene roca, al extraerlo una vez obtenemos roca. El coste de desecharla es $C_i$.

Utilizamos una excavadora para la extracción de la siguiente manera. Primero elegimos dos rectas paralelas en el plano $xy$. Después extraemos todo el oro y toda la roca, una vez cada uno, en la región comprendida entre las dos rectas paralelas (incluidos el oro o la roca situados sobre ellas).

El beneficio de JOI Kingdom es el valor total del oro en la región de extracción menos el coste total de desechar la roca de esa misma región. Queremos maximizar el beneficio de JOI Kingdom.

Tarea

Escribe un programa que calcule el beneficio máximo de JOI Kingdom.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea de la entrada contiene un entero $N$, el número de puntos de los que podemos extraer oro o roca.

• La línea $i$ ($1 \le i \le N$) de las siguientes $N$ líneas contiene tres enteros separados por espacios, $X_i$, $Y_i$, $W_i$.

  • Si $W_i \ge 1$, el punto $i$, $(X_i,Y_i)$, contiene oro. Al extraerlo una vez obtenemos oro de valor $V_i=W_i$.
  • Si $W_i \le -1$, el punto $i$, $(X_i,Y_i)$, contiene roca. Al extraerlo una vez obtenemos roca, y el coste de desecharla es $C_i=-W_i$.

  Se cumple $W_i \ne 0$.

Salida

Escribe una línea en la salida estándar. La salida contiene el beneficio máximo de JOI Kingdom.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

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

Subtareas

Hay 5 subtareas. La puntuación y las restricciones adicionales de cada subtarea son las siguientes:

Subtarea 1 [5 puntos]

• $N \le 100$.
• $Y_i=0$ ($1 \le i \le N$). En otras palabras, todos los puntos están sobre el eje $x$.

Subtarea 2 [20 puntos]

• $N \le 100$.
• No hay tres puntos distintos que estén sobre una misma recta.
• Sea $L$ una recta del plano $xy$ que pasa por dos puntos distintos. Sea $L'$ otra recta, distinta de $L$, del plano $xy$ que pasa por dos puntos distintos. Entonces, $L$ y $L'$ no son paralelas entre sí.

Subtarea 3 [35 puntos]

• No hay tres puntos distintos que estén sobre una misma recta.
• Sea $L$ una recta del plano $xy$ que pasa por dos puntos distintos. Sea $L'$ otra recta, distinta de $L$, del plano $xy$ que pasa por dos puntos distintos. Entonces, $L$ y $L'$ no son paralelas entre sí.

Subtarea 4 [20 puntos]

• No hay tres puntos distintos que estén sobre una misma recta.

Subtarea 5 [20 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

19

Nota

En la entrada de ejemplo 1, las posiciones del oro y la roca en JOI Kingdom son las siguientes.

En esta entrada de ejemplo, podemos extraer oro o roca en los puntos $2$, $3$, $4$, $5$. Entonces, el beneficio de JOI Kingdom es $19$. Este es el beneficio máximo de JOI Kingdom.

Entrada 2

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

Salida 2

15

Nota

En la entrada de ejemplo 2, los puntos $1$, $2$, $3$ están sobre una misma recta. Además, los puntos $4$, $5$, $6$ están sobre una misma recta.

Entrada 3

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

Salida 3

5

Nota

En la entrada de ejemplo 3, no hay tres puntos distintos que estén sobre una misma recta. Sea $L$ una recta que pasa por los puntos $1$ y $2$, y sea $L'$ una recta 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

Nota

Es posible elegir una región sin oro ni roca. En la entrada de ejemplo 4, el beneficio máximo 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