Maximum Unique Node Weight Path in a Directed Graph

You are given a directed graph with n nodes and m edges. Each node has an associated weight. Your task is to find a path (which may revisit nodes and edges arbitrarily) such that the sum of the weights of the nodes in the path is maximized. Note that if a node is visited multiple times, its weight is counted only once.

More formally:

Let the nodes be numbered from 1 to n with weights \(w_1, w_2, \dots, w_n\). You are given m directed edges. You need to choose a path \(v_1 \to v_2 \to \ldots \to v_k\) (where each consecutive pair is connected by a directed edge) such that the sum \(\sum_{v \in U} w_v\) is maximized, where \(U\) is the set of distinct vertices in the path.

You are required to output the maximum weight sum achievable by such a path.

Hint: Since nodes can be repeated in the path but their weight is counted only once, think about the maximum set of nodes that you can

inputFormat

The first line contains two integers n and m, representing the number of nodes and the number of directed edges.

The second line contains n integers, where the i-th integer is the weight of node i (\(w_i\)).

The following m lines each contain two integers u and v, denoting a directed edge from node u to node v.

Note that the nodes are 1-indexed.

outputFormat

Output a single integer, the maximum sum of unique node weights along any valid path.

sample

5 6
1 2 3 4 5
1 2
2 3
3 1
2 4
4 5
5 4

15