H - 收集物品

得分：$600$ 分

问题描述

有一个有 $N$ 个顶点和 $M$ 条边的有向图。
顶点编号为 $1, \dots, 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$

输出

输出结果。

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