配点 : $600$ 点

問題文

$N$ 頂点 $M$ 辺の有向グラフがあります。 頂点は $1, \dots, N$ と番号付けられており、$i \, (1 \leq i \leq M)$ 番目の辺は頂点 $A_i$ から頂点 $B_i$ に向けて張られています。

はじめ、頂点 $i \, ( 1 \leq i \leq N)$ には $X_i$ 個の落とし物があります。これらの落とし物を $K$ 人で拾うことになりました。

$K$ 人は $1$ 人ずつグラフ上を移動します。各々は次のような行動をとります。

• 頂点 $1$ から出発し、辺をたどって移動することを任意の有限回繰り返す。訪れた各頂点（頂点 $1$ も含む）について、落とし物がまだ拾われていなければ、全て拾う。

合計で最大何個の落とし物を拾うことができるか求めてください。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq K \leq 10$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$
• $i \neq j$ ならば、$A_i \neq A_j$ または $B_i \neq B_j$
• $1 \leq X_i \leq 10^9$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

$X_1$ $\ldots$ $X_N$

出力

答えを出力せよ。

5 5 2
1 2
2 3
3 2
1 4
1 5
1 4 5 2 8

18

$2$ 人がそれぞれ次のように行動することで、$18$ 個の落とし物を拾うことができます。

• $1$ 人目は、頂点 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ の順に移動し、頂点 $1, 2, 3$ にある落とし物を拾う。
• $2$ 人目は、頂点 $1 \rightarrow 5$ の順に移動し、頂点 $5$ にある落とし物を拾う。

$19$ 個以上の落とし物を拾うことはできないので、$18$ を出力します。

3 1 10
2 3
1 100 100

1