A cactus graph is defined as a connected, undirected graph with no self-loops or multiple edges, where every edge belongs to at most one simple cycle (a cycle that does not pass through the same vertex twice).

Cactus graph (left), not a cactus graph (middle, middle edge belongs to two cycles), not a cactus graph (right, not a connected graph)

Given $n$ points in the plane, the $i$-th point has coordinates $(x_i, y_i)$. Given $m$ edges, the $i$-th edge connects vertices $u_i, v_i$. It is guaranteed that the undirected graph formed by these $n$ points and $m$ edges is a cactus graph.

Initially, all $m$ edges are white. You can choose a subset of edges and color them black. The cost of coloring the $i$-th edge black is $w_i$.

For every pair of edges of different colors that share a common vertex, if we start from the white edge and rotate counter-clockwise around the common vertex by $x$ edges to reach the black edge, we gain $p \times x$ energy. Specifically, for two collinear edges with the same direction (i.e., the other vertices have the same polar angle with respect to the common vertex), we define the one reached first as the one with the smaller index; that is, the edge with the smaller index has a smaller polar angle.

Calculate the maximum value of the total energy gained minus the total cost of coloring.

Input

The input is read from the file color.in.

The first line contains three positive integers $n, m, p$, representing the number of vertices, the number of edges, and the coefficient for energy gain, respectively.

The next $m$ lines each contain three integers $u_i, v_i, w_i$, representing the vertices and the cost of the $i$-th edge.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th point.

Output

The output is written to the file color.out.

Output a single integer representing the maximum value of the total energy gained minus the total cost of coloring.

Examples

Input 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

Output 1

38

Note 1

As shown in the figure below, the solid black lines represent edges colored black, and the gray dotted lines represent edges that remain white.

After spending a cost of $2$ to color $(3, 4)$ black, rotating counter-clockwise around vertex $4$ by $1$ edge from $(1, 4)$ reaches $(3, 4)$, gaining $10 \times 1 = 10$ energy; rotating counter-clockwise around vertex $3$ by $1$ edge from $(2, 3)$ reaches $(3, 4)$ (note: according to the problem description, $(3, 4)$ is reached before $(3, 5)$), gaining $10 \times 1 = 10$ energy; rotating counter-clockwise around vertex $3$ by $2$ edges from $(3, 5)$ reaches $(3, 4)$, gaining $10 \times 2 = 20$ energy. Therefore, the total energy gained after coloring is $10 + 10 + 20 = 40$, the total cost is $2$, and the maximum value sought is $40 - 2 = 38$.

It can be proven that no coloring scheme yields a larger answer.

Examples 2

See color/color2.in and color/color2.ans in the contestant directory.

Subtasks

For all test data, it is guaranteed that: $2 \le n, m \le 2 \times 10^5$, $1 \le p \le 1000$, $\forall 1 \le i \le m, 1 \le u_i, v_i \le n, 0 \le w_i \le 10^4$, $\forall 1 \le i \le n, 0 \le x_i, y_i \le 10^7$, The given graph is a cactus graph; * No two points have the same coordinates.

Special Property A: Guaranteed that $m = n - 1$, i.e., the given graph is a tree.

Special Property B: Guaranteed that any pair of edges without a common vertex in the given graph do not intersect in the plane, i.e., the given graph is a planar embedding.

Special Property C: Guaranteed that $\forall 1 \le i \le m, w_i = 0$.

Special Property D: Guaranteed that $\forall 1 \le i \le m, w_i = 1, p = 1$.