P2811 Protect the school

Last time, the security staff’s status was on the line because of the cow incident. They decided to guard the school properly this time, and they have a plan. But since the campus is too large, they cannot plan it well, so they come to you again for help. Please solve their problem so they can resume their mobile gaming journey.

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.

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 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.

$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