Nieskierowany, spójny graf bez pętli i krawędzi wielokrotnych nazywamy kaktusem wtedy i tylko wtedy, gdy każda jego krawędź należy do co najwyżej jednego cyklu prostego. Cykl prosty to cykl bez powtarzających się wierzchołków.

Kaktus; nie jest kaktusem (środkowa krawędź należy do dwóch cykli); nie jest kaktusem (graf nie jest spójny).

Danych jest $n$ punktów na płaszczyźnie. Punkt $i$ ma współrzędne $(x_i,y_i)$. Danych jest również $m$ krawędzi; krawędź $i$ łączy wierzchołki $u_i,v_i$. Gwarantuje się, że graf nieskierowany złożony z tych $n$ punktów i $m$ krawędzi jest kaktusem.

Początkowo wszystkie $m$ krawędzi są białe. Możesz wybrać pewne krawędzie i pokolorować je na czarno. Koszt pokolorowania krawędzi $i$ na czarno wynosi $w_i$.

Dla każdej pary krawędzi różnych kolorów, które mają wspólny wierzchołek, niech $x$ oznacza liczbę krawędzi, o które trzeba obrócić się wokół wspólnego wierzchołka przeciwnie do ruchu wskazówek zegara, zaczynając od białej krawędzi, aby dotrzeć do czarnej. Za taką parę uzyskuje się energię $p\times x$. W szczególności, dla dwóch współliniowych krawędzi o tym samym kierunku (czyli takich, których drugie końce mają ten sam kąt biegunowy względem wspólnego wierzchołka) przyjmujemy, że najpierw napotykamy krawędź o mniejszym numerze, to znaczy ma ona mniejszy kąt biegunowy.

Znajdź największą możliwą różnicę między sumą uzyskanej energii a łącznym kosztem kolorowania.

Wejście

Dane należy odczytać z pliku color.in.

Pierwszy wiersz zawiera trzy dodatnie liczby całkowite $n,m,p$, oznaczające odpowiednio liczbę wierzchołków, liczbę krawędzi oraz współczynnik uzyskiwanej energii.

W kolejnych $m$ wierszach, w wierszu $i$, podane są trzy liczby całkowite $u_i,v_i,w_i$, opisujące końce i koszt krawędzi $i$.

W kolejnych $n$ wierszach, w wierszu $i$, podane są dwie liczby całkowite $x_i,y_i$, czyli współrzędne punktu $i$.

Wyjście

Wynik należy zapisać do pliku color.out.

Wypisz w jednym wierszu jedną liczbę całkowitą: największą możliwą różnicę między sumą energii uzyskanej po kolorowaniu a łącznym kosztem kolorowania.

Przykład

Wejście 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

Wyjście 1

38

Uwagi

Na poniższym rysunku czarna linia ciągła oznacza krawędź pokolorowaną na czarno, a szare linie kropkowane oznaczają krawędzie, które pozostały białe.

Po pokolorowaniu krawędzi $(3,4)$ na czarno za koszt $2$, obrót od $(1,4)$ wokół wierzchołka $4$ przeciwnie do ruchu wskazówek zegara o $1$ krawędź prowadzi do $(3,4)$ i daje energię $10\times1=10$. Obrót od $(2,3)$ wokół wierzchołka $3$ przeciwnie do ruchu wskazówek zegara o $1$ krawędź również prowadzi do $(3,4)$ (uwaga: zgodnie z ustaloną regułą najpierw napotykamy $(3,4)$, a dopiero potem $(3,5)$), co daje energię $10\times1=10$. Obrót od $(3,5)$ wokół wierzchołka $3$ przeciwnie do ruchu wskazówek zegara o $2$ krawędzie prowadzi do $(3,4)$ i daje energię $10\times2=20$. Zatem łączna uzyskana energia wynosi $10+10+20=40$, łączny koszt to $2$, a szukana największa wartość to $40-2=38$. Można udowodnić, że żadne kolorowanie nie daje większego wyniku.

Przykład 2

Zobacz pliki color/color2.in i color/color2.ans w katalogu zawodnika.

Podzadania

Dla wszystkich danych testowych gwarantuje się:

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

• Dla każdego $1\le i\le m$: $1\le u_i,v_i\le n$, $0\le w_i\le10^4$;

• Dla każdego $1\le i\le n$: $0\le x_i,y_i\le10^7$;

• Dany graf jest kaktusem;

• Żadne dwa punkty nie mają tych samych współrzędnych.

Własność szczególna A: $m=n-1$, czyli dany graf jest drzewem.

Własność szczególna B: żadne dwie krawędzie danego grafu, które nie mają wspólnego wierzchołka, nie przecinają się na płaszczyźnie, czyli dany graf ma osadzenie planarne.

Własność szczególna C: dla każdego $1\le i\le m$ zachodzi $w_i=0$.

Własność szczególna D: dla każdego $1\le i\le m$ zachodzi $w_i=1$, a ponadto $p=1$.