Notes

Skr has a lovely home with a rather exquisite garden. In his garden, Skr has many apple trees. It is almost summer time, and the apples are about to mature, but being the impatient type, Skr does not want to wait for the apples to fall from the trees. That is why, he decides to throw tiny pebblestones to the trees in order to cause the apples to fall.

All the trees in Skr's garden has a structure similar to the tree data structure he sees frequently in the competitive programming contests he enters. The root node is located at the ground level, and every separation of branches indicate a node. Unlike ordinary apple trees, the apples on the trees in Skr's garden are strictly located at the nodes, and there are no apples on the branches of any tree. Note that the trees in Skr's garden do not have to be balanced.

Skr wants to throw pebblestones at the nodes of his trees, so that some of the apples fall. He is an excellent shot, so he will never miss. When he throws a stone to a node j, all the apples within the subtree rooted at j will fall down.

Skr has only K stones, and you are asked to help him compute the maximum amount of apples he can collect, given the structure of his trees.

Input:
The first line of the input indicate the numbers N, M and K. N represents the total number of nodes in the gardenm and M represents the total number of edges (i.e. branches) between those nodes. K is the number of pebblestones Skr has.

On the following line, there are N integers representing the number of apples on the nodes. The i^th integer represents the number of apples on node with index i.

Each of the following M lines feature integers u and v, indicating that there is an edge from node with index u to node with index v.

It is guaranteed that the structure provided will be a forest with single or multiple trees.

Output:
Print the maximum number of apples Skr can collect from his garden.

Bounds:
N <= 1,000,000
M <= 1,000,000
K <= 1,000,000
1 <= u, v <= N


Solution:
O(V + E) => Find roots (ones with 0 incoming edges)
O(V + E) => DFS to find out the number of apples in each subtree

O(K * logV + V log V) => Priority queue to select K elements (K * logV)
When an element is selected, remove all of its subtree from the priority queue (V * logV)