Description

The school has $n$ checkpoints. Because the guards do not want to think too hard, they decide to build $m$ passages between these $n$ checkpoints. Due to lax administration and militarized management, these roads are one-way; going in the reverse direction will result in punishment.

The guards are short-handed (too many game quests), so they will select some checkpoints to stand guard. Since the guards have special skills, a guard can instantly traverse along any path reachable from the checkpoint where he is stationed (i.e., teleport to any vertex reachable via directed edges). Each checkpoint has a value representing its difficulty.

To protect the school, please help them ensure that if an incident occurs at any checkpoint, at least one guard can instantly reach it. For convenience and easier management, tell them the minimum possible total difficulty under the constraint of using the fewest number of guards.

Input Format

The first line contains an integer $n$, the number of checkpoints.

The second line contains $n$ integers, the difficulties of the checkpoints.

The third line contains an integer $m$, the number of roads.

Each of the next $m$ lines contains two integers $u, v$, indicating a one-way passage from $u$ to $v$.

Output Format

Output two integers.

The first integer is the minimum total difficulty. The second integer is the number of valid selections that achieve both the minimum number of guards and that minimum total difficulty.

5
31619 26195 18669 1198 178
4
2 4
3 5
1 2
4 1

20045 1

Hint

$1 \le n \le 10^4$, $1 \le m \le 5 \times 10^4$, and the answer fits in the int range.

Translated by ChatGPT 5