Le royaume de JOI est réputé pour sa production d'or. Une fois par an, on y utilise un bulldozer pour extraire de l'or.

Le territoire du royaume de JOI est représenté par un plan muni de coordonnées $xy$. Il contient $N$ sites. Le $i$-ième site ($1 \le i \le N$) se trouve en $(X_i,Y_i)$. Chaque site contient soit de l'or, soit de la roche, mais pas les deux.

Si le site $i$ contient de l'or, l'exploiter une fois rapporte de l'or de valeur $V_i$. Si le site $i$ contient de la roche, l'exploiter une fois produit de la roche, dont l'évacuation coûte $C_i$.

Nous utilisons un bulldozer pour l'extraction de la manière suivante. Nous choisissons d'abord deux droites parallèles dans le plan $xy$. Ensuite, nous extrayons tout l'or et toute la roche de la zone située entre ces deux droites, une fois pour chaque site, y compris l'or ou la roche situés sur ces droites.

Le bénéfice du royaume de JOI est la valeur totale de l'or dans la zone exploitée, moins le coût total d'évacuation de la roche dans cette même zone. Nous souhaitons maximiser ce bénéfice.

Tâche

Écrivez un programme qui calcule le bénéfice maximal du royaume de JOI.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient un entier $N$, le nombre de sites où l'on peut extraire de l'or ou de la roche.

• La $i$-ième ligne ($1 \le i \le N$) parmi les $N$ lignes suivantes contient trois entiers $X_i$, $Y_i$, $W_i$ séparés par des espaces.

  • Si $W_i \ge 1$, le $i$-ième site $(X_i,Y_i)$ contient de l'or. L'exploiter une fois rapporte de l'or de valeur $V_i=W_i$.
  • Si $W_i \le -1$, le $i$-ième site $(X_i,Y_i)$ contient de la roche. L'exploiter une fois produit de la roche, dont l'évacuation coûte $C_i=-W_i$.

  On a $W_i \ne 0$.

Sortie

Écrivez une ligne sur la sortie standard, contenant le bénéfice maximal du royaume de JOI.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Il y a 5 sous-tâches. Le score et les contraintes supplémentaires de chacune sont les suivants.

Sous-tâche 1 [5 points]

• $N \le 100$.
• $Y_i=0$ ($1 \le i \le N$). Autrement dit, tous les sites sont situés sur l'axe des $x$.

Sous-tâche 2 [20 points]

• $N \le 100$.
• Aucun triplet de sites distincts n'est aligné.
• Soit $L$ une droite du plan $xy$ passant par deux sites distincts. Soit $L'$ une autre droite du plan $xy$, différente de $L$, passant par deux sites distincts. Alors $L$ et $L'$ ne sont pas parallèles.

Sous-tâche 3 [35 points]

• Aucun triplet de sites distincts n'est aligné.
• Soit $L$ une droite du plan $xy$ passant par deux sites distincts. Soit $L'$ une autre droite du plan $xy$, différente de $L$, passant par deux sites distincts. Alors $L$ et $L'$ ne sont pas parallèles.

Sous-tâche 4 [20 points]

• Aucun triplet de sites distincts n'est aligné.

Sous-tâche 5 [20 points]

Il n'y a aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

19

Remarque

Dans l'exemple d'entrée 1, les positions de l'or et de la roche dans le royaume de JOI sont les suivantes.

Dans cet exemple, nous pouvons extraire de l'or ou de la roche aux sites $2$, $3$, $4$, $5$. Le bénéfice du royaume de JOI est alors de $19$. C'est le bénéfice maximal du royaume de JOI.

Entrée 2

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

Sortie 2

15

Remarque

Dans l'exemple d'entrée 2, les sites $1$, $2$, $3$ sont alignés. Les sites $4$, $5$, $6$ le sont également.

Entrée 3

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

Sortie 3

5

Remarque

Dans l'exemple d'entrée 3, aucun triplet de sites distincts n'est aligné. Soit $L$ la droite passant par les sites $1$ et $2$, et $L'$ la droite passant par les sites $3$ et $4$. Alors $L$ et $L'$ sont parallèles.

Entrée 4

2
0 0 -1
1 0 -1

Sortie 4

0

Remarque

Il est possible de choisir une zone sans or ni roche. Dans l'exemple d'entrée 4, le bénéfice maximal est $0$.

Entrée 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

Sortie 5

107