AT_abc214_h [ABC214H] Collecting

有一个包含 $N$ 个顶点、$M$ 条边的有向图。 顶点编号为 $1,\dots,N$，第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$。 一开始，第 $i$ 个顶点上有 $X_i$ 个遗失物品。现在有 $K$ 个人要去捡这些遗失物品。 $K$ 个人会依次在图上移动。每个人的行动如下： - 从顶点 $1$ 出发，沿着边任意次移动。每到达一个顶点（包括顶点 $1$），如果该顶点上的遗失物品还没有被捡走，则全部捡走。 请你求出最多可以捡到多少个遗失物品。

输入按以下格式从标准输入给出。 > $N$ $M$ $K$ > $A_1$ $B_1$ > $\vdots$ > $A_M$ $B_M$ > $X_1$ $\ldots$ $X_N$

请输出答案。

### 限制条件 - $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$ - 所有输入均为整数。 ### 样例解释 1 两个人可以按如下方式行动，最多捡到 $18$ 个遗失物品。 - 第一个人按 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ 的顺序移动，捡走顶点 $1, 2, 3$ 上的遗失物品。 - 第二个人按 $1 \rightarrow 5$ 的顺序移动，捡走顶点 $5$ 上的遗失物品。 无法捡到超过 $19$ 个遗失物品，因此输出 $18$。 由 ChatGPT 4.1 翻译