Problem Description

In JOI Kingdom, there are $N$ islands, numbered from $1$ to $N$. Each island has an insecurity level $S_i$.

In JOI Kingdom, ships are used as the primary mode of transportation between islands. There are $M$ ships, numbered from $1$ to $M$. The $j$-th ship connects islands $A_j$ and $B_j$. These ships can be operated as needed, allowing travel from any island to any other island by taking multiple ships.

Today, Prime Minister K has decided to introduce new ships and requires all ships to adhere to the following security condition:

• When a ship is anchored at island $i$ (where $1 \leq i \leq N$), the number of security guards on the ship must be greater than or equal to $S_i$.

Given the high cost of hiring security guards, we aim to minimize the total number of guards hired. As long as the condition "it is possible to travel from any island to any other island by taking multiple ships" is met, some of the currently operating ships can be abolished.

We will operate the ships as follows, where $k$ is the number of new ships to be introduced:

1. For each of the $k$ new ships, choose the two islands it connects.
2. Abolish a number of (greater than or equal to $0$) ships, including newly introduced ones.
3. For each ship, anchor it at one of the two connected islands and place a certain number of security guards on it. This must satisfy the condition that for every pair of islands $u$ and $v$ (where $1 \leq u, v \leq N$), a passenger can be transported from island $u$ to island $v$ by repeating the following operations:
   - Board a passenger or security guards on a ship anchored at the current island.
   - Disembark a passenger or security guards at the island where the ship is currently anchored.
   - Move the ship from the current island to the connected island.

Due to budget constraints, we can introduce at most $Q$ new ships. For each $k$ (where $0 \leq k \leq Q$), Prime Minister K wants to know the minimum possible number of hired security guards when $k$ new ships are introduced. Write a program to calculate this for each $k$ based on the given information about islands, ship routes, and the number of new ships that can be introduced.

Input Format

Read the following data from the standard input:

• The first line contains three integers $N$, $M$, and $Q$.
• The second line contains $N$ integers $S_1, S_2, \ldots, S_N$.
• The next $M$ lines contain two integers each, $A_j$ and $B_j$, representing the islands connected by the $j$-th ship.

Output Format

Write $Q+1$ lines to the standard output. The $(k+1)$-th line (where $0 \leq k \leq Q$) should contain the minimum possible number of hired security guards when $k$ new ships are introduced.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

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

Sample Output #2

7
5

Sample Input #3

3 3 0
1 1 1
1 2
1 3
2 3

Sample Output #3

2

Sample Input #4

8 7 0
2 2 2 2 2 2 2 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

Sample Output #4

14

Sample Input #5

8 7 0
16 39 36 23 15 48 23 56
1 2
1 3
2 4
2 5
3 6
3 7
7 8

Sample Output #5

245

Sample Input #6

10 13 4
314 159 265 358 979 323 846 264 338 327
1 2
1 4
2 3
2 5
3 6
4 5
4 7
5 6
5 8
6 9
7 8
8 9
9 10

Sample Output #6

3139
2901
2722
2567
2461

Notes/Hints

Sample Explanation #1

If no new ships are introduced, we need 7 security guards. For example, the conditions are satisfied if we allocate the ships and 7 security guards as follows:

• Ship 1 is anchored at island 2 with 2 security guards.
• Ship 2 is anchored at island 2 with 2 security guards.
• Ship 3 is anchored at island 4 with 3 security guards.

Sample Explanation #2

If no new ships are introduced, similarly to Sample Input 1, we need 7 security guards. If one new ship is introduced, we need 5 security guards. For example, the conditions are satisfied if we allocate the ships and 5 security guards as follows:

• Introduce a new ship connecting islands 2 and 4 (referred to as ship 4).
• Abolish ship 3.
• Anchor ship 1 at island 2 with 2 security guards.
• Anchor ship 2 at island 2 with 1 security guard.
• Anchor ship 4 at island 2 with 2 security guards.

Sample Explanation #3

If no new ships are introduced, we need 2 security guards. For example, the conditions are satisfied if we allocate the ships and 2 security guards as follows:

• Abolish ship 3.
• Anchor ship 1 at island 1 with 1 security guard.
• Anchor ship 2 at island 1 with 1 security guard.

Sample Explanation #4

This sample input satisfies the constraints of all subtasks.

Sample Explanation #5

This sample input satisfies the constraints of Subtasks 3, 4, 5, 6, 7.

Sample Explanation #6

This sample input satisfies the constraints of Subtasks 5, 6, 7.

Data Range

For all test data, the following constraints apply:

• $2 \leq N \leq 2 \times 10^5$
• $N - 1 \leq M \leq 4 \times 10^5$
• $0 \leq Q \leq 2 \times 10^5$
• $1 \leq S_i \leq 10^9$ (for $1 \leq i \leq N$)
• $1 \leq A_j < B_j \leq N$ (for $1 \leq j \leq M$)
• $(A_x, B_x) \neq (A_y, B_y)$ (for $1 \leq x < y \leq M$)
• It is possible to travel from any island to any other island by taking multiple ships.
• All given values are integers.

Subtasks

见题面 Input 部分

见题面 Output 部分