自己ループも多重辺もない無向連結グラフについて、どの辺も高々 1 つの単純閉路にしか属さないとき、かつそのときに限り、そのグラフをカクタスグラフと定義します。ここで単純閉路とは、同じ頂点を重複して通らない閉路です。

左：カクタスグラフ。中央：カクタスグラフではない（中央の辺が 2 つの閉路に属する）。右：カクタスグラフではない（連結グラフではない）。

平面上の $n$ 個の点が与えられ、$i$ 番目の点の座標は $(x_i,y_i)$ です。また、$m$ 本の辺が与えられ、$i$ 番目の辺は頂点 $u_i,v_i$ を結びます。これらの $n$ 個の点と $m$ 本の辺からなる無向グラフはカクタスグラフであることが保証されます。

最初、$m$ 本の辺はすべて白色です。いくつかの辺を選び、黒色に塗ることができます。$i$ 番目の辺を黒色に塗るコストは $w_i$ です。

共通の頂点をもつ異なる色の辺の各組について、白い辺から共通の頂点を中心として反時計回りに $x$ 本の辺だけ回ると黒い辺に到達する場合、$p\times x$ のエネルギーを得られます。特に、同一直線上で同じ向きの 2 本の辺、すなわち共通の頂点から見たもう一方の頂点の偏角が等しい辺については、番号の小さい辺に先に到達するものとします。つまり、番号の小さい辺の偏角が小さいものとします。

色を塗った後に得られるエネルギーの総和から、塗るコストの総和を引いた値の最大値を求めてください。

入力

ファイル color.in から入力してください。

最初の行には 3 つの正整数 $n,m,p$ が与えられ、それぞれ頂点数、辺数、エネルギーを得る際の係数を表します。

続く $m$ 行のうち $i$ 行目には 3 つの整数 $u_i,v_i,w_i$ が与えられ、$i$ 番目の辺の端点とコストを表します。

続く $n$ 行のうち $i$ 行目には 2 つの整数 $x_i,y_i$ が与えられ、$i$ 番目の点の座標を表します。

出力

ファイル color.out に出力してください。

色を塗った後に得られるエネルギーの総和から、塗るコストの総和を引いた値の最大値を、1 行に 1 つの整数として出力してください。

入出力例

入力 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,5)$ より先に $(3,4)$ に到達することに注意してください）、$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$。
• すべての $1\le i\le m$ について、$1\le u_i,v_i\le n,\ 0\le w_i\le10^4$。
• すべての $1\le i\le n$ について、$0\le x_i,y_i\le10^7$。
• 与えられるグラフはカクタスグラフです。
• どの 2 点も座標が一致しません。

特殊な性質 A：$m=n-1$、すなわち与えられるグラフが木であることが保証されます。

特殊な性質 B：共通の頂点をもたない辺のどの組も平面上で交差しないこと、すなわち与えられるグラフが平面に埋め込まれていることが保証されます。

特殊な性質 C：すべての $1\le i\le m$ について $w_i=0$ が保証されます。

特殊な性質 D：すべての $1\le i\le m$ について $w_i=1$ であり、$p=1$ が保証されます。