Maximum Toys Collection

In the Land of Kattis, children play an exciting game where they traverse a directed graph to collect as many toys as possible. The game starts at node 1, and each node may contain a certain number of toys. A move is allowed from a node u to a node v if there is a directed edge from u to v. Each node can be visited at most once. The objective is to maximize the total number of toys collected along a valid path starting at node 1.

The problem can be mathematically formulated as finding the maximum sum along a path in a directed acyclic graph. Formally, if we denote by \(T_i\) the number of toys at node \(i\) and the existence of a directed edge from \(u\) to \(v\) by \(u \rightarrow v\), the goal is to compute:

[ \max_{\text{valid path starting at }1} \sum_{i \text{ in path}} T_i ]

You are given the number of nodes, the number of edges, an array representing the toy count at each node, and a list of directed edges. Your task is to compute the maximum number of toys that can be collected starting from node 1.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of nodes and edges respectively. The second line contains \(n\) integers where the \(i\)-th integer represents the number of toys at node \(i\). Then, \(m\) lines follow; each contains two integers \(u\) and \(v\), representing a directed edge from node \(u\) to node \(v\>.

outputFormat

Output a single integer representing the maximum number of toys that can be collected starting from node 1.

4 4
5 1 10 0
1 2
1 3
2 4
3 4

15