题目描述

有一个有$N$个顶点和$M$条边的有向图。
顶点编号为$1, \ldots, N$，第$i$条边$(1 \leq i \leq M)$从顶点$A_i$指向顶点$B_i$。

初始时，顶点$i$上有$X_i$个失落的物品$(1 \leq i \leq N)$。$K$个人将收集这些物品。

这$K$个人会依次在图中行走。每个人需要进行以下操作：

• 从顶点$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$
• $A_i \neq A_j$ 或 $B_i \neq B_j$，其中 $i \neq 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$

输出

打印答案。

示例输入 1

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

示例输出 1

18

两个人可以按以下方式收集到$18$个物品：

• 第一个人经过路径$1 \rightarrow 2 \rightarrow 3 \rightarrow 2$，并收集到顶点$1$、$2$和$3$上的物品。
• 第二个人经过路径$1 \rightarrow 5$，并收集到顶点$5$上的物品。

无法收集到$19$个或更多物品，因此输出$18$。

示例输入 2

3 1 10
2 3
1 100 100

示例输出 2

1