O reino JOI é famoso pela produção de ouro. Uma vez por ano, utiliza-se um trator de esteiras no reino JOI para extrair ouro.

O território do reino JOI é descrito por um plano com coordenadas $xy$. Há $N$ pontos no território. O $i$-ésimo ponto ($1 \le i \le N$) é $(X_i,Y_i)$. Cada ponto contém ouro ou rocha, mas não ambos.

Se o ponto $i$ contém ouro, ao explorá-lo uma vez obtemos ouro de valor $V_i$. Se o ponto $i$ contém rocha, ao explorá-lo uma vez obtemos rocha. O custo para descartá-la é $C_i$.

Utilizamos um trator de esteiras para a extração da seguinte maneira. Primeiro, escolhemos duas retas paralelas no plano $xy$. Depois, extraímos todo o ouro e toda a rocha na região entre as duas retas paralelas, uma vez para cada um (incluindo o ouro ou a rocha que se encontram sobre elas).

O lucro do reino JOI é o valor total do ouro na região de extração menos o custo total de descarte da rocha nessa mesma região. Queremos maximizar o lucro do reino JOI.

Tarefa

Escreva um programa que calcule o lucro máximo do reino JOI.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha da entrada contém um inteiro $N$, o número de pontos onde podemos obter ouro ou rocha.

• A $i$-ésima linha ($1 \le i \le N$) das $N$ linhas seguintes contém três inteiros $X_i$, $Y_i$, $W_i$, separados por espaços.

  • Se $W_i \ge 1$, o $i$-ésimo ponto $(X_i,Y_i)$ contém ouro. Ao explorá-lo uma vez, obtemos ouro de valor $V_i=W_i$.
  • Se $W_i \le -1$, o $i$-ésimo ponto $(X_i,Y_i)$ contém rocha. Ao explorá-lo uma vez, obtemos rocha, cujo custo de descarte é $C_i=-W_i$.

  É garantido que $W_i \ne 0$.

Saída

Escreva uma linha na saída padrão. A saída deve conter o lucro máximo do reino JOI.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Há 5 subtarefas. A pontuação e as restrições adicionais de cada subtarefa são as seguintes:

Subtarefa 1 [5 pontos]

• $N \le 100$.
• $Y_i=0$ ($1 \le i \le N$). Em outras palavras, todos os pontos estão sobre o eixo $x$.

Subtarefa 2 [20 pontos]

• $N \le 100$.
• Não há três pontos distintos sobre uma mesma reta.
• Seja $L$ uma reta no plano $xy$ que passa por dois pontos distintos. Seja $L'$ outra reta, diferente de $L$, no plano $xy$, que passa por dois pontos distintos. Então, $L$ e $L'$ não são paralelas entre si.

Subtarefa 3 [35 pontos]

• Não há três pontos distintos sobre uma mesma reta.
• Seja $L$ uma reta no plano $xy$ que passa por dois pontos distintos. Seja $L'$ outra reta, diferente de $L$, no plano $xy$, que passa por dois pontos distintos. Então, $L$ e $L'$ não são paralelas entre si.

Subtarefa 4 [20 pontos]

• Não há três pontos distintos sobre uma mesma reta.

Subtarefa 5 [20 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

19

Explicação

Na Entrada de Exemplo 1, as posições do ouro e da rocha no reino JOI são as seguintes.

Ouro (Gold); Rocha (Rock).

Neste exemplo de entrada, podemos obter ouro ou rocha nos pontos $2$, $3$, $4$, $5$. Assim, o lucro do reino JOI é $19$. Este é o lucro máximo do reino JOI.

Entrada 2

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

Saída 2

15

Explicação

Na Entrada de Exemplo 2, os pontos $1$, $2$, $3$ estão sobre uma mesma reta. Da mesma forma, os pontos $4$, $5$, $6$ estão sobre uma mesma reta.

Entrada 3

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

Saída 3

5

Explicação

Na Entrada de Exemplo 3, não há três pontos distintos sobre uma mesma reta. Seja $L$ uma reta que passa pelos pontos $1$ e $2$, e seja $L'$ uma reta que passa pelos pontos $3$ e $4$. Então, $L$ e $L'$ são paralelas entre si.

Entrada 4

2
0 0 -1
1 0 -1

Saída 4

0

Explicação

É possível escolher uma região sem ouro nem rocha. Na Entrada de Exemplo 4, o lucro máximo é $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

Saída 5

107