分数: 600 点
问题陈述
有一个有向图 N 顶点和 M 边缘。
顶点已编号 1, \dots, N,以及 i第边缘 (1 \leq i \leq M) 来自顶点 A_i 到顶点 B_i.
最初,有 Vertex 上的 X_i 项目 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 or 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 并收集 Vertex 上的物品 5.
无法收集 19 或更多项目,所以我们应该打印 18.
示例输入 2
3 1 10 2 3 1 100 100
示例输出 2
1