{"raw_statement":[{"iden":"problem statement","content":"There is a directed graph with $N$ vertices and $M$ edges.  \nThe 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$.\nInitially, there are $X_i$ items on Vertex $i$ $(1 \\leq i \\leq N)$ that someone has lost. $K$ people will collect these items.\nThe $K$ people will travel in the graph one by one. Each person will do the following.\n\n*   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.\n\nFind the maximum total number of items that can be collected."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq K \\leq 10$\n*   $1 \\leq A_i, B_i \\leq N$\n*   $A_i \\neq B_i$\n*   $A_i \\neq A_j$ or $B_i \\neq B_j$, if $i \\neq j$.\n*   $1 \\leq X_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $B_1$\n$\\vdots$\n$A_M$ $B_M$\n$X_1$ $\\ldots$ $X_N$"},{"iden":"sample input 1","content":"5 5 2\n1 2\n2 3\n3 2\n1 4\n1 5\n1 4 5 2 8"},{"iden":"sample output 1","content":"18\n\nThe two people can collect $18$ items as follows.\n\n*   The first person goes $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 2$ and collects the items on Vertices $1$, $2$, and $3$.\n*   The second person goes $1 \\rightarrow 5$ and collects the items on Vertex $5$.\n\nIt is impossible to collect $19$ or more items, so we should print $18$."},{"iden":"sample input 2","content":"3 1 10\n2 3\n1 100 100"},{"iden":"sample output 2","content":"1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}