Guard Deployment Optimization

A school has n checkpoints and m one-way corridors connecting them. Due to lazy security and rigid management, the corridors are directed; traveling in the reverse direction is forbidden. There is a shortage of guards, so they decide to station guards at only some checkpoints. Each guard, having special skills, can instantly teleport via any path starting from his checkpoint (i.e. he can reach any checkpoint that is reachable from his stationed checkpoint).

Each checkpoint has an associated difficulty value. In order to secure the entire school, the goal is to ensure that for every checkpoint, there exists at least one guard who can instantly reach it through the network of corridors. Among all ways to cover the network using the minimum number of guards, you are asked to choose the deployment with the smallest total sum of difficulty values of the selected checkpoints.

Note: If the checkpoints and corridors are modeled as a directed graph, the solution is to decompose the graph into strongly connected components (SCCs). In the condensation graph (which is a DAG) the source components (with no incoming edges) must each have a guard. The answer is the sum of the minimum difficulty values in each of these source SCCs.

Mathematical formulation:

If we denote by \(S = \{C_1, C_2, \dots, C_k\}\) the set of source SCCs in the condensation graph and by \(d(i)\) the difficulty of checkpoint i, then for each source SCC \(C_j\) compute \(min_{i \in C_j} d(i)\) and the answer is \(\sum_{j=1}^k \min_{i \in C_j} d(i)\).

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5), representing the number of checkpoints and the number of one-way corridors, respectively.

The second line contains n space-separated integers, where the i-th integer represents the difficulty value of checkpoint i.

Each of the following m lines contains two integers u and v (1 ≤ u, v ≤ n), meaning there is a one-way corridor from checkpoint u to checkpoint v.

outputFormat

Output a single integer: the minimum total difficulty sum of checkpoints where guards are placed, ensuring that every checkpoint can be reached from at least one stationed guard via the corridors using the minimum number of guards.

sample

3 3
1 2 3
1 2
2 3
3 1

1