Surviving Symbols - Repovive Premier Round 8 | Repovive

24F. Surviving Symbols

3000 pts3s256 MB

You have a sequence $s$ of length $n$ , initially equal to $(1,2,\ldots,n)$ .

For each symbol $i$ , you are given a positive integer $a_i$ , its value.

There are $m$ commands. Command $j$ is specified by two distinct symbols $x_j$ and $y_j$ . Executing it simultaneously replaces every current occurrence of $x_j$ in $s$ with $y_j$ . If $x_j$ does not occur in $s$ , the sequence remains unchanged, but the command still counts as executed.

You may execute a finite sequence of commands in any order. Each command may be executed multiple times, but every given command must be executed at least once.

Let $D$ be the set of symbols occurring in $s$ after you finish. The final value is $\sum_{i\in D} a_i$ : each distinct symbol contributes its value exactly once, regardless of its number of occurrences.

Find the maximum possible final value.

Constraints

$1 \le t \le 10$
$1 \le n \le 500$
$0 \le m \le n(n-1)$
$1 \le a_i \le 10^9$
$1 \le x_j,y_j \le n$
$x_j \ne y_j$
The ordered pairs $(x_j,y_j)$ are pairwise distinct within each test case.
The sum of $n$ over all test cases is at most $500$ .

Input

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_m \quad y_m \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Explanation

Case 1

Execute $2\to3$ , then $1\to2$ . The final sequence is $(2,3,3)$ , with value $5+3=8$ . Symbol $1$ must be absent at the end because its outgoing command must be executed and no command can produce it.

Case 2

Execute $1\to2$ , $3\to1$ , $2\to3$ , and $1\to2$ again. The final sequence is $(3,3,2)$ , with value $6+9=15$ . The first command executed makes at least one symbol absent, and the number of distinct symbols can never increase. Since the smallest symbol value is $4$ , the value cannot exceed $4+9+6-4=15$ .

Output

Case 1

Case 2

Input

Case 1

4 0
1000000000 7 1000000000 3

Case 2

Case 3

Explanation

Case 1

There are no commands, so every symbol remains present. Their total value is $2000000010$ .

Case 2

Execute $3\to4$ , $4\to3$ , $3\to4$ , $1\to3$ , $1\to2$ , $2\to1$ , and $1\to2$ . The final sequence is $(3,2,4,4)$ , so the value is $5+8+9=22$ . The command $1\to2$ executed while $1$ is absent still counts as executed. At least one symbol must become absent, so losing only the smallest value, $2$ , is optimal.

Case 3

Execute $2\to3$ , $3\to2$ , $2\to3$ , $1\to2$ , $1\to4$ , $4\to5$ , $5\to4$ , and $4\to5$ . The final sequence is $(2,3,3,5,5)$ , with value $4+8+7=19$ .

Symbol $1$ must be absent at the end. Each of the pairs $\{2,3\}$ and $\{4,5\}$ must lose a symbol when one of its internal commands is first executed. Only a command with source $1$ can restore a missing symbol in either pair, and such a command can change the sequence at most once. Therefore at least one additional symbol must remain absent. The shown execution loses values $10$ and $3$ , the smallest possible total loss.

Output

Case 1

2000000010

Case 2

Case 3

You have a sequence $s$ of length $n$ , initially equal to $(1,2,\ldots,n)$ .

For each symbol $i$ , you are given a positive integer $a_i$ , its value.

You may execute a finite sequence of commands in any order. Each command may be executed multiple times, but every given command must be executed at least once.

Find the maximum possible final value.

$1 \le t \le 10$
$1 \le n \le 500$
$0 \le m \le n(n-1)$
$1 \le a_i \le 10^9$
$1 \le x_j,y_j \le n$
$x_j \ne y_j$
The ordered pairs $(x_j,y_j)$ are pairwise distinct within each test case.
The sum of $n$ over all test cases is at most $500$ .

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_m \quad y_m \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

There are no commands, so every symbol remains present. Their total value is $2000000010$ .

Execute $2\to3$ , $3\to2$ , $2\to3$ , $1\to2$ , $1\to4$ , $4\to5$ , $5\to4$ , and $4\to5$ . The final sequence is $(2,3,3,5,5)$ , with value $4+8+7=19$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

24F. Surviving Symbols

Constraints

Input

Output

Samples

24F. Surviving Symbols

Constraints

Input

Output

Samples