Description

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.

Input Format

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 Format

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

2 2
1 1
1 2
2 1

2

Hint

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.

Translated by ChatGPT 5