P3387 [Template] SCC Condensation

Given a directed graph with $n$ vertices and $m$ edges, each vertex has a weight. Find a path such that the sum of the weights of the vertices visited is maximized. You only need to output this sum. You are allowed to traverse an edge or a vertex multiple times. However, if a vertex is visited repeatedly, its weight is counted only once.

The first line contains two positive integers $n, m$. The second line contains $n$ integers, where the $i$-th number $a_i$ is the weight of vertex $i$. Lines 3 through $m+2$ each contain two integers $u, v$, indicating a directed edge $u \rightarrow v$.

Output a single line with the maximum sum of vertex weights.

Constraints: For $100\%$ of the testdata, $1 \le n \le 10^4$, $1 \le m \le 10^5$, $0 \le a_i \le 10^3$. - 2024-11-1 Added [hack testdata](https://www.luogu.com.cn/discuss/964940). Translated by ChatGPT 5