Un grafo no dirigido y conexo, sin bucles ni aristas múltiples, se denomina grafo cactus si y solo si cada arista pertenece como máximo a un ciclo simple. Un ciclo simple es un ciclo que no repite vértices.

De izquierda a derecha: grafo cactus; no es un grafo cactus (la arista central pertenece a dos ciclos); no es un grafo cactus (no es conexo).

Se dan $n$ puntos del plano; las coordenadas del punto $i$ son $(x_i,y_i)$. También se dan $m$ aristas; la arista $i$ une los vértices $u_i,v_i$. Se garantiza que el grafo no dirigido formado por estos $n$ puntos y $m$ aristas es un grafo cactus.

Inicialmente, las $m$ aristas son blancas. Puedes elegir algunas aristas y pintarlas de negro. Pintar de negro la arista $i$ tiene un coste $w_i$.

Para cada par de aristas de distinto color que comparten un vértice, sea $x$ el número de aristas que se recorren al girar en sentido antihorario alrededor del vértice común, partiendo de la arista blanca hasta llegar a la negra. Entonces se obtiene una energía de $p\times x$. En particular, para dos aristas colineales con la misma dirección (es decir, cuyos otros extremos tienen el mismo ángulo polar respecto al vértice común), se establece que primero se alcanza la de menor índice; en otras palabras, se considera que la arista de menor índice tiene menor ángulo polar.

Halla el máximo valor de la energía total obtenida tras pintar las aristas menos el coste total de pintarlas.

Entrada

Lee los datos del archivo color.in.

La primera línea contiene tres enteros positivos $n,m,p$: el número de vértices, el número de aristas y el coeficiente de la energía obtenida, respectivamente.

Las siguientes $m$ líneas describen las aristas: la línea $i$ contiene tres enteros $u_i,v_i,w_i$, los extremos y el coste de la arista $i$.

Las siguientes $n$ líneas describen los puntos: la línea $i$ contiene dos enteros $x_i,y_i$, las coordenadas del punto $i$.

Salida

Escribe la salida en el archivo color.out.

Escribe una línea con un entero: el máximo valor de la energía total obtenida tras pintar las aristas menos el coste total de pintarlas.

Ejemplos

Entrada 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

Salida 1

38

Nota

En la siguiente figura, la línea continua negra representa la arista pintada de negro y las líneas de puntos grises representan las aristas que siguen siendo blancas.

Tras pagar un coste de $2$ para pintar $(3,4)$ de negro, desde $(1,4)$ se llega a $(3,4)$ girando en sentido antihorario $1$ arista alrededor del vértice $4$, y se obtiene una energía de $10\times1=10$. Desde $(2,3)$ se llega a $(3,4)$ girando en sentido antihorario $1$ arista alrededor del vértice $3$ (observa que, según la regla del enunciado, se alcanza $(3,4)$ antes que $(3,5)$), y se obtiene una energía de $10\times1=10$. Desde $(3,5)$ se llega a $(3,4)$ girando en sentido antihorario $2$ aristas alrededor del vértice $3$, y se obtiene una energía de $10\times2=20$. Por tanto, la energía total obtenida es $10+10+20=40$, el coste total es $2$ y el máximo solicitado es $40-2=38$. Se puede demostrar que no existe una forma de pintar las aristas con un resultado mayor.

Ejemplo 2

Consulta los archivos color/color2.in y color/color2.ans del directorio del concursante.

Subtareas

Para todos los datos de prueba se garantiza lo siguiente:

• $2\le n,m\le2\times10^5$, $1\le p\le1000$.

• Para todo $1\le i\le m$, $1\le u_i,v_i\le n$ y $0\le w_i\le10^4$.

• Para todo $1\le i\le n$, $0\le x_i,y_i\le10^7$.

• El grafo dado es un grafo cactus.

• No hay dos puntos con las mismas coordenadas.

Propiedad especial A: se garantiza que $m=n-1$; es decir, el grafo dado es un árbol.

Propiedad especial B: se garantiza que ningún par de aristas sin un vértice común se cruza en el plano; es decir, se da una inmersión plana del grafo.

Propiedad especial C: se garantiza que $w_i=0$ para todo $1\le i\le m$.

Propiedad especial D: se garantiza que $w_i=1$ para todo $1\le i\le m$, y $p=1$.