Maximum Collectable Value in a Directed Acyclic Graph

You are given a directed acyclic graph (DAG) with \( n \) nodes and \( m \) edges. Each node has an associated integer value. Starting from any node, you can traverse the graph by following the directed edges, and you are allowed to visit each node at most once. Your task is to determine the maximum total value that can be collected along any valid path.

If you visit nodes \( i_1, i_2, \ldots, i_k \) along the path, the total collected value is given by:

[ \sum_{j=1}^{k} value_{i_j} ]

Note that the input graph is guaranteed to be a DAG, so a topological order exists. You can use techniques such as dynamic programming along the topologically sorted nodes to solve this problem.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two space-separated integers \( n \) and \( m \), representing the number of nodes and edges, respectively.
2. The second line contains \( n \) space-separated integers, where the \( i^{th} \) integer denotes the value of node \( i \).
3. The next \( m \) lines each contain two space-separated integers \( u \) and \( v \), indicating a directed edge from node \( u \) to node \( v \).

If \( n = 0 \), there are no node values or edges.

outputFormat

Output a single integer to standard output (stdout): the maximum collectable value by following a valid directed path in the graph.

4 3
5 10 20 15
1 2
2 3
3 4

50