{"problem":{"name":"Collecting","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc214_h"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc214_h","tags":[],"sample_group":[["5 5 2\n1 2\n2 3\n3 2\n1 4\n1 5\n1 4 5 2 8","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$."],["3 1 10\n2 3\n1 100 100","1"]],"created_at":"2026-03-03 11:01:13"}}