一個冇自環、冇重邊嘅無向連通圖，當且僅當佢嘅任何一條邊最多屬於一個簡單環，就稱為仙人掌圖。簡單環係指唔經過重複節點嘅環。

仙人掌圖；唔係仙人掌圖（中間嗰條邊喺兩個環上）；唔係仙人掌圖（唔係連通圖）。

畀定平面上嘅 $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$。