Description

Fusu was deeply moved by the story of the painter and the koi. In order to let the koi and the painter continue living together, he decided to return to the burning courtyard and put out the fire.

The painter’s courtyard can be abstracted as a directed graph. Each node represents a burning location. To measure the size of the fire, Fusu assigns each node a fire value. The larger the fire value, the stronger the fire at that node.

Wind helps the fire, and the fire borrows the wind’s force. For each burning node, strong wind may cause the fire to spread to other nodes. Each directed edge $<u,v>$ in the graph represents that the fire spreads from node $u$ to node $v$. Note that one node may spread to many nodes, and it may also be formed by fires spreading together from many nodes.

To avoid the painter noticing that someone is helping to put out the fire, at any moment, Fusu is not allowed to extinguish the fire at any node that is not being spread to by any node. After a node’s fire is extinguished, all outgoing edges representing the spread from that node will disappear. Note that although the edges disappear, all properties of the nodes that it spreads to, except for their in-degrees, will not change, and they will not disappear.

Because the time for time travel is limited, Fusu can extinguish the fire of at most $k$ nodes. He wants to ask you what is the maximum total fire value he can extinguish.

Simplified statement:

Given a directed graph where each node has a weight. At any moment, you may choose any node with in-degree, gain its weight, and delete it and its outgoing edges from the graph. You may choose at most $k$ nodes. Find the maximum total weight you can obtain.

Input Format

The first line contains three integers separated by spaces, representing the number of nodes $n$, the number of edges $m$, and the limit on the number of chosen nodes $k$.

The second line contains $n$ integers separated by spaces. The $i$-th integer $w_i$ represents the fire value (node weight) of node $i$.

Lines $3$ to $(m + 2)$ each contain two integers $u, v$ separated by spaces, representing a directed edge from $u$ to $v$.

Output Format

Output one line with one integer, representing the maximum total fire value.

7 7 3
10 2 8 4 9 5 7
1 2
1 3
1 4
2 5
3 6
3 7
4 7

24

Hint

Explanation for Sample Input/Output 1

Choose nodes $3, 5, 7$.

Constraints

This problem uses bundled testdata with a total of $5$ subtasks.

• Subtask 1 (30 points): $n = 10$, $m = 50$.
• Subtask 2 (30 points): $n = 100001$, $m = 500001$. It is guaranteed that the given graph is a directed acyclic graph.
• Subtask 3 (20 points): $n = 100002$, $m = 500002$. It is guaranteed that in the given graph, there is one and only one node with in-degree $0$.
• Subtask 4 (17 points): $n = 100003$, $m = 500003$.
• Subtask 5 (3 points): $n = 500004$, $m = 2000004$.

For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^5 + 4$, $1 \leq m \leq 2 \times 10^6 + 4$, $0 \leq w_i \leq 10^3$, $0 \leq k \leq n$.

It is not guaranteed that the given graph has no self-loops.

Notes

• Please pay attention to the impact of input reading on program efficiency.
• The last digit of $n$ can help you quickly determine which subtask the test point belongs to.

Translated by ChatGPT 5