Score : $600$ points
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.
Find the maximum total number of items that can be collected.
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$
Print the answer.
5 5 2 1 2 2 3 3 2 1 4 1 5 1 4 5 2 8
18
The two people can collect $18$ items as follows.
It is impossible to collect $19$ or more items, so we should print $18$.
3 1 10 2 3 1 100 100
1