Ein zusammenhängender, ungerichteter Graph ohne Schleifen und Mehrfachkanten heißt genau dann Kaktusgraph, wenn jede seiner Kanten zu höchstens einem einfachen Kreis gehört. Ein einfacher Kreis ist ein Kreis, der keinen Knoten mehrfach durchläuft.

Links: Kaktusgraph. Mitte: kein Kaktusgraph (die mittlere Kante gehört zu zwei Kreisen). Rechts: kein Kaktusgraph (nicht zusammenhängend).

Gegeben sind $n$ Punkte in der Ebene. Der $i$-te Punkt hat die Koordinaten $(x_i,y_i)$. Außerdem sind $m$ Kanten gegeben; die $i$-te Kante verbindet die Knoten $u_i,v_i$. Es ist garantiert, dass der aus diesen $n$ Punkten und $m$ Kanten bestehende ungerichtete Graph ein Kaktusgraph ist.

Anfangs sind alle $m$ Kanten weiß. Du kannst einige Kanten auswählen und schwarz färben. Die Kosten für das Schwarzfärben der $i$-ten Kante betragen $w_i$.

Betrachte jedes Paar verschiedenfarbiger Kanten mit einem gemeinsamen Knoten. Wenn man ausgehend von der weißen Kante um den gemeinsamen Knoten gegen den Uhrzeigersinn um $x$ Kanten weiterdrehen muss, um die schwarze Kante zu erreichen, erhält man $p\times x$ Energie. Für zwei kollineare Kanten mit gleicher Richtung (deren jeweils anderer Endpunkt also bezüglich des gemeinsamen Knotens denselben Polarwinkel hat) wird insbesondere festgelegt, dass die Kante mit der kleineren Nummer zuerst erreicht wird. Das heißt, die Kante mit der kleineren Nummer hat den kleineren Polarwinkel.

Gesucht ist der größtmögliche Wert der gesamten nach dem Färben erhaltenen Energie abzüglich der gesamten Färbekosten.

Eingabe

Lies die Daten aus der Datei color.in.

Die erste Eingabezeile enthält drei positive ganze Zahlen $n,m,p$: die Anzahl der Knoten, die Anzahl der Kanten und den Koeffizienten der erhaltenen Energie.

Es folgen $m$ Zeilen. Die $i$-te davon enthält drei ganze Zahlen $u_i,v_i,w_i$, die die Endknoten und die Kosten der $i$-ten Kante angeben.

Es folgen $n$ Zeilen. Die $i$-te davon enthält zwei ganze Zahlen $x_i,y_i$, die die Koordinaten des $i$-ten Punktes angeben.

Ausgabe

Schreibe die Ausgabe in die Datei color.out.

Gib in einer Zeile eine ganze Zahl aus: den größtmöglichen Wert der gesamten nach dem Färben erhaltenen Energie abzüglich der gesamten Färbekosten.

Beispiele

Eingabe 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

Ausgabe 1

38

Hinweis

In der folgenden Abbildung stellen schwarze durchgezogene Linien schwarz gefärbte Kanten dar; graue gepunktete Linien stellen weiterhin weiße Kanten dar.

Färbt man $(3,4)$ mit Kosten $2$ schwarz, erreicht man von $(1,4)$ aus durch Drehen gegen den Uhrzeigersinn um $1$ Kante um Knoten $4$ die Kante $(3,4)$ und erhält $10\times1=10$ Energie. Von $(2,3)$ aus erreicht man durch Drehen gegen den Uhrzeigersinn um $1$ Kante um Knoten $3$ die Kante $(3,4)$ (beachte: Nach der Festlegung in der Aufgabenstellung wird $(3,4)$ vor $(3,5)$ erreicht) und erhält $10\times1=10$ Energie. Von $(3,5)$ aus erreicht man durch Drehen gegen den Uhrzeigersinn um $2$ Kanten um Knoten $3$ die Kante $(3,4)$ und erhält $10\times2=20$ Energie. Die gesamte nach dem Färben erhaltene Energie beträgt daher $10+10+20=40$, die Gesamtkosten betragen $2$, und der gesuchte Maximalwert ist $40-2=38$. Man kann beweisen, dass es keine Färbung mit einem größeren Ergebnis gibt.

Beispiel 2

Siehe color/color2.in und color/color2.ans im Teilnehmerverzeichnis.

Teilaufgaben

Für alle Testdaten ist garantiert:

• $2\le n,m\le2\times10^5$, $1\le p\le1000$;
• für alle $1\le i\le m$: $1\le u_i,v_i\le n$, $0\le w_i\le10^4$;
• für alle $1\le i\le n$: $0\le x_i,y_i\le10^7$;
• der gegebene Graph ist ein Kaktusgraph;
• keine zwei Punkte haben dieselben Koordinaten.

Besondere Eigenschaft A: Es gilt $m=n-1$, der gegebene Graph ist also ein Baum.

Besondere Eigenschaft B: Je zwei Kanten des gegebenen Graphen ohne gemeinsamen Knoten schneiden sich in der Ebene nicht. Der gegebene Graph ist also planar eingebettet.

Besondere Eigenschaft C: Für alle $1\le i\le m$ gilt $w_i=0$.

Besondere Eigenschaft D: Für alle $1\le i\le m$ gilt $w_i=1$, und es gilt $p=1$.