Minimum Cost with Dependencies

You are given n activities (numbered from 1 to n) and m dependency relations. Each activity has an associated positive cost. A dependency (a, b) indicates that activity a must be completed before activity b can begin. Your task is to determine whether it is possible to perform all activities while respecting these dependencies. If it is, output the total cost (which is the sum of the costs of all activities); otherwise, output \( -1 \).

Note: Dependencies form a directed graph. The total cost remains the sum of the individual costs if a valid ordering exists, regardless of the activity order.

The problem can be formally stated as follows:

Given:

• \( n \) - the number of activities,
• \( m \) - the number of dependency relations,
• A list of \( n \) positive integers \( c_1, c_2, \dots, c_n \) representing the cost of each activity,
• A list of \( m \) ordered pairs \( (a, b) \) indicating activity \( a \) must precede activity \( b \).

Output \( \sum_{i=1}^{n}c_i \) if a valid ordering (i.e. a topological sort) exists, otherwise output \( -1 \).

inputFormat

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

 n m
 c1 c2 ... cn
 a1 b1
 a2 b2
 ...
 am bm

Where:

• The first line contains two integers: n (the number of activities) and m (the number of dependencies).
• The second line contains n positive integers where the \( i^{th} \) integer represents the cost of activity i.
• The next m lines each contain two integers a and b indicating that activity a must be performed before activity b.

outputFormat

Output the total cost (sum of all activity costs) if it is possible to complete all activities while respecting the dependencies; otherwise, output -1.

The output should be written to standard output (stdout).

## sample

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

17