H - Collecting Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の有向グラフがあります。
頂点は 1, \dots, N と番号付けられており、i \, (1 \leq i \leq M) 番目の辺は頂点 A_i から頂点 B_i に向けて張られています。

はじめ、頂点 i \, ( 1 \leq i \leq N) には X_i 個の落とし物があります。これらの落とし物を K 人で拾うことになりました。

K 人は 1 人ずつグラフ上を移動します。各々は次のような行動をとります。

  • 頂点 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
  • i \neq j ならば、A_i \neq A_j または B_i \neq B_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

2 人がそれぞれ次のように行動することで、18 個の落とし物を拾うことができます。

  • 1 人目は、頂点 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 の順に移動し、頂点 1, 2, 3 にある落とし物を拾う。
  • 2 人目は、頂点 1 \rightarrow 5 の順に移動し、頂点 5 にある落とし物を拾う。

19 個以上の落とし物を拾うことはできないので、18 を出力します。

入力例 2

3 1 10
2 3
1 100 100

出力例 2

1

Score : 600 points

Problem Statement

There is a directed graph with N vertices and M edges.
The vertices are numbered 1, \dots, N, and the i-th edge (1 \leq i \leq M) goes from Vertex A_i to Vertex B_i.

Initially, there are X_i items on Vertex i (1 \leq i \leq N) that someone has lost. K people will collect these items.

The K people will travel in the graph one by one. Each person will do the following.

  • Start on Vertex 1. Then, traverse an edge any finite number of times. For each vertex visited (including Vertex 1), collect all items on it if they have not been collected yet.

Find the maximum total number of items that can be collected.

Constraints

  • 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, if i \neq j.
  • 1 \leq X_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
X_1 \ldots X_N

Output

Print the answer.

Sample Input 1

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

Sample Output 1

18

The two people can collect 18 items as follows.

  • The first person goes 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 and collects the items on Vertices 1, 2, and 3.
  • The second person goes 1 \rightarrow 5 and collects the items on Vertex 5.

It is impossible to collect 19 or more items, so we should print 18.

Sample Input 2

3 1 10
2 3
1 100 100

Sample Output 2

1