#abc214h. [abc214_h]Collecting

[abc214_h]Collecting

题目描述

有一个有NN个顶点和MM条边的有向图。
顶点编号为1,,N1, \ldots, N,第ii条边(1iM)(1 \leq i \leq M)从顶点AiA_i指向顶点BiB_i

初始时,顶点ii上有XiX_i个失落的物品(1iN)(1 \leq i \leq N)KK个人将收集这些物品。

KK个人会依次在图中行走。每个人需要进行以下操作:

  • 从顶点11出发,然后沿着一条边行走任意次数。对于访问过的每个顶点(包括顶点11),如果该顶点上的物品尚未被收集,则将其收集起来。

请找出可收集的物品的最大总数。

约束条件

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 1M2×1051 \leq M \leq 2 \times 10^5
  • 1K101 \leq K \leq 10
  • 1Ai,BiN1 \leq A_i, B_i \leq N
  • AiBiA_i \neq B_i
  • AiAjA_i \neq A_jBiBjB_i \neq B_j,其中 iji \neq j
  • 1Xi1091 \leq X_i \leq 10^9
  • 输入中的所有值都是整数。

输入

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

NN MM KK A1A_1 B1B_1 \vdots AMA_M BMB_M X1X_1 \ldots XNX_N

输出

打印答案。


示例输入 1

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

示例输出 1

18

两个人可以按以下方式收集到1818个物品:

  • 第一个人经过路径12321 \rightarrow 2 \rightarrow 3 \rightarrow 2,并收集到顶点112233上的物品。
  • 第二个人经过路径151 \rightarrow 5,并收集到顶点55上的物品。

无法收集到1919个或更多物品,因此输出1818


示例输入 2

3 1 10
2 3
1 100 100

示例输出 2