← 返回题目列表

AtCoder · abc214_h

H. 收集

中文机器翻译题面 查看原题

分数: 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