On appelle graphe cactus un graphe non orienté connexe, sans boucle ni arête multiple, si et seulement si chacune de ses arêtes appartient à au plus un cycle simple. Un cycle simple est un cycle qui ne passe pas deux fois par le même sommet.

À gauche : un cactus. Au milieu : pas un cactus (l’arête centrale appartient à deux cycles). À droite : pas un cactus (le graphe n’est pas connexe).

On vous donne $n$ points du plan ; les coordonnées du point $i$ sont $(x_i,y_i)$. On vous donne également $m$ arêtes ; l’arête $i$ relie les sommets $u_i$ et $v_i$. Il est garanti que le graphe non orienté formé par ces $n$ points et ces $m$ arêtes est un cactus.

Initialement, les $m$ arêtes sont toutes blanches. Vous pouvez choisir plusieurs arêtes et les colorier en noir. Colorier l’arête $i$ en noir coûte $w_i$.

Pour chaque paire d’arêtes de couleurs différentes ayant un sommet commun, supposons qu’en partant de l’arête blanche et en tournant dans le sens inverse des aiguilles d’une montre autour du sommet commun, on atteigne l’arête noire après avoir avancé de $x$ arêtes. On gagne alors une énergie de $p\times x$. En particulier, pour deux arêtes colinéaires de même direction (c’est-à-dire dont les autres extrémités ont le même angle polaire par rapport au sommet commun), on convient d’atteindre d’abord l’arête de plus petit numéro ; autrement dit, l’arête de plus petit numéro a un angle polaire plus petit.

Déterminez la valeur maximale de la somme des énergies obtenues après coloration, diminuée de la somme des coûts de coloration.

Entrée

Les données sont lues dans le fichier color.in.

La première ligne contient trois entiers strictement positifs $n,m,p$, représentant respectivement le nombre de sommets, le nombre d’arêtes et le coefficient de gain d’énergie.

Les $m$ lignes suivantes contiennent chacune trois entiers $u_i,v_i,w_i$ à la ligne $i$, représentant les extrémités et le coût de l’arête $i$.

Les $n$ lignes suivantes contiennent chacune deux entiers $x_i,y_i$ à la ligne $i$, représentant les coordonnées du point $i$.

Sortie

Écrivez la réponse dans le fichier color.out.

Affichez sur une ligne un entier : la valeur maximale de la somme des énergies obtenues après coloration, diminuée de la somme des coûts de coloration.

Exemples

Entrée 1

5 4 10
1 4 1
2 3 2
3 4 2
3 5 2
0 1
1 1
0 0
1 0
2 0

Sortie 1

38

Remarque

Sur la figure ci-dessous, les traits noirs continus représentent les arêtes coloriées en noir, tandis que les pointillés gris représentent les arêtes restées blanches.

Après avoir colorié $(3,4)$ en noir pour un coût de $2$, on atteint $(3,4)$ depuis $(1,4)$ en avançant de $1$ arête dans le sens inverse des aiguilles d’une montre autour du sommet $4$, ce qui rapporte une énergie de $10\times1=10$. Depuis $(2,3)$, on atteint $(3,4)$ en avançant de $1$ arête dans le sens inverse des aiguilles d’une montre autour du sommet $3$ (attention : selon la convention de l’énoncé, on atteint $(3,4)$ avant $(3,5)$), ce qui rapporte une énergie de $10\times1=10$. Depuis $(3,5)$, on atteint $(3,4)$ en avançant de $2$ arêtes dans le sens inverse des aiguilles d’une montre autour du sommet $3$, ce qui rapporte une énergie de $10\times2=20$. La somme des énergies obtenues après coloration est donc $10+10+20=40$, et le coût total est $2$. Le maximum recherché vaut $40-2=38$. On peut montrer qu’aucune coloration ne donne une réponse plus grande.

Exemple 2

Voir color/color2.in et color/color2.ans dans le répertoire des candidats.

Sous-tâches

Pour tous les jeux de test, il est garanti que :

• $2\le n,m\le2\times10^5$, $1\le p\le1000$ ;
• $\forall 1\le i\le m$, $1\le u_i,v_i\le n$, $0\le w_i\le10^4$ ;
• $\forall 1\le i\le n$, $0\le x_i,y_i\le10^7$ ;
• le graphe donné est un cactus ;
• deux points distincts n’ont jamais les mêmes coordonnées.

Propriété particulière A : il est garanti que $m=n-1$, c’est-à-dire que le graphe donné est un arbre.

Propriété particulière B : il est garanti que deux arêtes du graphe donné n’ayant pas de sommet commun ne se coupent pas dans le plan ; autrement dit, le graphe donné est plongé dans le plan.

Propriété particulière C : il est garanti que $\forall 1\le i\le m$, $w_i=0$.

Propriété particulière D : il est garanti que $\forall 1\le i\le m$, $w_i=1$, et $p=1$.