收集

题目描述

有一个 $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$),如果其上的物品还没有被收集过,则全部收集。

求最多能收集到的物品总数。

输入格式

输入按以下格式从标准输入给出：

$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

两个人可以如下收集 $18$ 个物品。

第一个人走 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$,收集了顶点 $1$、$2$、$3$ 上的物品。

第二个人走 $1 \rightarrow 5$,收集了顶点 $5$ 上的物品。

不可能收集到 $19$ 个及以上物品,因此应输出 $18$。

3 1 10
2 3
1 100 100

1

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le K \le 10$
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• 当 $i \neq j$ 时,$A_i \neq A_j$ 或 $B_i \neq B_j$
• $1 \le X_i \le 10^9$
• 输入均为整数