题目描述
有一个有N个顶点和M条边的有向图。
顶点编号为1,…,N,第i条边(1≤i≤M)从顶点Ai指向顶点Bi。
初始时,顶点i上有Xi个失落的物品(1≤i≤N)。K个人将收集这些物品。
这K个人会依次在图中行走。每个人需要进行以下操作:
- 从顶点1出发,然后沿着一条边行走任意次数。对于访问过的每个顶点(包括顶点1),如果该顶点上的物品尚未被收集,则将其收集起来。
请找出可收集的物品的最大总数。
约束条件
- 2≤N≤2×105
- 1≤M≤2×105
- 1≤K≤10
- 1≤Ai,Bi≤N
- Ai=Bi
- Ai=Aj 或 Bi=Bj,其中 i=j。
- 1≤Xi≤109
- 输入中的所有值都是整数。
输入
从标准输入中按以下格式给出输入:
N M K
A1 B1
⋮
AM BM
X1 … XN
输出
打印答案。
示例输入 1
示例输出 1
两个人可以按以下方式收集到18个物品:
- 第一个人经过路径1→2→3→2,并收集到顶点1、2和3上的物品。
- 第二个人经过路径1→5,并收集到顶点5上的物品。
无法收集到19个或更多物品,因此输出18。
示例输入 2
示例输出 2