定義一個無自環、無重邊的無向連通圖為仙人掌圖，若且唯若其中任意一條邊至多屬於一個簡單環，其中簡單環指不經過重複節點的環。

給定平面上的 $n$ 個點，第 $i$ 個點的座標為 $(x_i,y_i)$。給定 $m$ 條邊，第 $i$ 條邊連接節點 $u_i,v_i$。保證由這 $n$ 個點與 $m$ 條邊構成的無向圖為仙人掌圖。

初始時，所有的 $m$ 條邊都是白色的。你可以選擇若干條邊，並將其染成黑色，其中將第 $i$ 條邊染成黑色的代價為 $w_i$。

對於每對有公共節點的異色邊，設從白色邊開始沿公共節點逆時針轉 $x$ 條邊可以到達黑色邊，那麼可以獲得 $p\times x$ 的能量。特別地，對於兩條共線且方向相同的邊（即另一節點相對於公共節點的極角相同的邊），規定先到達編號較小的邊，也就是編號較小的邊的極角更小。

求染色後可以獲得的能量總和減去染色代價總和的最大值。

輸入格式

從檔案 color.in 中讀入資料。

輸入的第一行有三個正整數 $n,m,p$，分別表示節點個數、邊數，以及獲得能量的係數。

接下來 $m$ 行，第 $i$ 行有三個整數 $u_i,v_i,w_i$，表示第 $i$ 條邊的節點與代價。

接下來 $n$ 行，第 $i$ 行有兩個整數 $x_i,y_i$，表示第 $i$ 個點的座標。

輸出格式

輸出到檔案 color.out 中。

輸出一行一個整數，表示染色後可以獲得的能量總和減去染色代價總和的最大值。

範例

輸入格式 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

輸出格式 1

38

說明

如下圖所示，黑色實線表示被染成黑色的邊，灰色點線表示仍為白色的邊。

花費 $2$ 的代價將 $(3,4)$ 染為黑色後，從 $(1,4)$ 沿節點 $4$ 逆時針轉 $1$ 條邊可以到達 $(3,4)$，獲得 $10\times1=10$ 能量；從 $(2,3)$ 沿節點 $3$ 逆時針轉 $1$ 條邊可以到達 $(3,4)$（注意：根據題目敘述中的規定，會先到達 $(3,4)$ 後到達 $(3,5)$），獲得 $10\times1=10$ 能量；從 $(3,5)$ 沿節點 $3$ 逆時針轉 $2$ 條邊可以到達 $(3,4)$，獲得 $10\times2=20$ 能量。因此染色後可以獲得的能量總和為 $10+10+20=40$，代價總和為 $2$，所求的最大值為 $40-2=38$。可以證明，不存在答案更大的染色方案。

範例 2

見選手目錄下的 color/color2.in 與 color/color2.ans。

子任務

對於所有測試資料，保證：

• $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$；
• 給定的圖是仙人掌圖；
• 任意兩個點的座標不重合。

特殊性質 A：保證 $m=n-1$，也就是給定的圖是一棵樹。

特殊性質 B：保證給定的圖上任意一對沒有公共節點的邊在平面上不相交，也就是給定的圖是平面嵌入。

特殊性質 C：保證 $\forall1\le i\le m$，$w_i=0$。

特殊性質 D：保證 $\forall1\le i\le m$，$w_i=1$，$p=1$。