Securing JOI Kingdom

In JOI Kingdom there are \(N\) islands numbered from \(1\) to \(N\), and each island \(i\) has an insecurity level \(S_i\). There are also \(M\) ships connecting islands; the ship \(j\) connects \(A_j\) and \(B_j\) and can be run as needed. It is known that one can travel between any two islands using some sequence of ships.

After an unfortunate incident, Prime Minister K has decided to introduce new ships. He demands that when a ship is anchored at island \(i\), the number of security guards on board is at least \(S_i\). Because hiring guards is expensive, the objective is to minimize the total number of hired guards while keeping the transportation network connected.

The procedure is as follows:

• First, choose \(k\ (0 \le k \le Q)\) new ships. For each new ship, select any pair of islands to connect.
• Then, from all ships (the original ones and the new ones), abolish any number of them (possibly including some of the new ones) as long as the remaining ships guarantee that for every pair of islands \(u,v\) there is a sequence of operations that can transport a passenger from \(u\) to \(v\). During these operations, the Security Condition must always be maintained.
• Finally, for each remaining ship, decide at which of its two endpoint islands it will be anchored, and put on board at least as many security guards as the insecurity level of that island.

The Security Condition requires that when a ship is anchored at island \(i\), it has at least \(S_i\) security guards.

Note that if a ship connects islands \(u\) and \(v\), you may choose the anchoring island to minimize the cost; in particular, the minimum number of guards required on that ship is \(\min(S_u, S_v)\). Also, new ships may be introduced between any pair of islands. However, if a new ship is used, it counts towards the budget (at most \(Q\) new ships may be introduced).

Your task is: For each \(k\) where \(0 \le k \le Q\), determine the minimum total number of security guards that need to be hired so that it is possible to choose a subset of the ships (from the original and newly introduced ones) satisfying the following:

• The remaining ships form a connected network (i.e. there is a route between any two islands using the remaining ships).
• For each ship, if it is anchored at island \(i\), it carries at least \(S_i\) security guards.

Observation: When a ship connecting islands \(u\) and \(v\) is used, you can choose the cheaper option, spending \(\min(S_u, S_v)\) guards on that ship. Also note that if island \(r\) has the smallest insecurity level \(S_r\), then a new ship connecting \(r\) to any other island would cost \(S_r\) guards. Thus, if new ships were unconstrained, the absolute lower bound on the cost would be a star graph centered at \(r\) with total cost \((N-1)\,S_r\). However, since only up to \(Q\) new ships can be introduced, you must use some of the original ships when \(k .

Input (detailed below) and Output formats are described in the following sections.

inputFormat

The input is given in the following format:

N M Q
S1 S2 ... SN
A1 B1
A2 B2
...
AM BM

Where:

• \(N\) is the number of islands.
• \(M\) is the number of original ships.
• \(Q\) is the maximum number of new ships that can be introduced.
• \(S_i\) is the insecurity level of island \(i\) (\(1 \le i \le N\)).
• Each of the next \(M\) lines contains two integers \(A_j\) and \(B_j\) (\(1 \le j \le M\)) indicating that ship \(j\) connects island \(A_j\) and island \(B_j\).

It is guaranteed that the original graph (with \(M\) ships) is connected.

outputFormat

Output \(Q+1\) integers in one line (or separated by spaces), where the \(k\)-th integer (starting from \(k = 0\)) represents the minimum total number of security guards required when exactly \(k\) new ships are introduced.

sample

3 3 1
3 2 4
1 2
2 3
1 3

4 4