Maximum Treasure Difference

In this problem, you are given a castle with N rooms. Each room contains a treasure with a certain value and there is a cost associated with traveling from one room to another. You are provided with an N×N cost matrix. For any two distinct rooms i and j, if there is a direct route from i to j (indicated by a cost not equal to -1), you may use it to travel from room i to room j. Your task is to find the maximum value of (\text{treasure}[j] - \text{cost} (i \rightarrow j)) over all pairs of rooms where there exists a path from room i to room j. The total travel cost is defined as the sum of the costs along the journey from the starting room to the destination room. In case no valid journey exists (for example, when N=1), output ( -\infty ) (displayed as -Infinity).

inputFormat

Input is given through standard input (stdin). The first line contains an integer N representing the number of rooms. The second line contains N space-separated integers, where the i-th integer represents the treasure value in room i (0-indexed). The next N lines each contain N space-separated integers. The j-th integer in the i-th line represents the cost of traveling from room i to room j. A cost of -1 indicates that there is no direct route between the rooms.

outputFormat

Output a single line to standard output (stdout) containing the maximum difference computed as the destination room's treasure value minus the computed travel cost along the route. If no journey is possible, output -Infinity.## sample

4
3 6 2 8
0 5 -1 10
-1 0 6 2
7 -1 0 3
4 12 -1 0

6