Maximum Coconuts Collection

Tony is an adventurer traveling through a series of islands. Each island contains a certain number of coconuts. The islands are connected by directed bridges. Starting from island 1 and aiming to reach island \( n \), Tony collects the coconuts available on each island he visits. His goal is to maximize the total number of coconuts collected along the way.

You are given an integer \( n \) representing the number of islands, an integer \( m \) representing the number of bridges, an array of \( n \) integers where the \( i \)-th integer denotes the number of coconuts on island \( i \), and \( m \) pairs of integers each representing a directed bridge from island \( u \) to island \( v \). Your task is to determine the maximum number of coconuts Tony can collect on a valid route from island 1 to island \( n \). If island \( n \) is unreachable, output "-inf".

The recurrence relation for computing the maximum number of coconuts collected is given by:

\[ dp[v] = \max(dp[v],\; dp[u] + \text{coconuts}[v]) \quad \text{for each bridge } (u,v) \text{ where } dp[u] \text{ is not } -\infty \]

Assume islands are numbered from 1 to \( n \), and all indices in the input follow this convention.

inputFormat

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

• The first line contains two integers \( n \) and \( m \), where \( n \) is the number of islands and \( m \) is the number of bridges.
• The second line contains \( n \) space-separated integers, where the \( i \)-th integer represents the number of coconuts on island \( i \).
• The next \( m \) lines each contain two space-separated integers \( u \) and \( v \) indicating a directed bridge from island \( u \) to island \( v \).

outputFormat

The output, written to stdout, is a single line containing the maximum number of coconuts Tony can collect from island 1 to island ( n ). If island ( n ) is unreachable, output "-inf".## sample

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

20