Problem Description

Kato is creating a scenario for a certain RPG. This RPG has \(N\) scenes, each of which is already determined to be either a "Battle" or a "Field". There are also \(M\) passageways connecting these scenes, where the \(i\)-th passageway allows movement from scene \(a_i\) to scene \(b_i\). Initially, the protagonist of the RPG, Shinya, is at scene \(1\), and he can freely move through the passageways to reach scene \(N\), which clears the game.

Shinya has two states: "Energetic" and "Fatigued". In the "Energetic" state, he can engage in battles, but in the "Fatigued" state, he cannot. Reaching a "Battle" scene in the "Fatigued" state results in a game over.

Shinya starts the game in the "Energetic" state. Passing through a "Battle" scene makes him tired and transitions him to the "Fatigued" state. To return to the "Energetic" state from the "Fatigued" state, he needs to pass through a "Resting Spot".

"Resting Spots" can be installed in any "Field" scene. The cost to install a resting spot at scene \(i \ (2 \leq i \leq N-1)\) is \(c_i\).

Currently, it is not decided where to install the "Resting Spots". Therefore, Kato decided to install the "Resting Spots" to satisfy the following conditions:

• No matter what path Shinya chooses to move from scene \(1\) to scene \(N\), he must pass through at least one "Resting Spot" between any two "Battle" scenes.
• Shinya's state at the game clear can be either "Fatigued" or "Energetic".

Find the minimum total cost required for Kato to install the "Resting Spots" to satisfy the above conditions. If it is impossible to satisfy the conditions no matter where the "Resting Spots" are installed, output -1.

Input Format

The input is given from the standard input in the following format:

\(N\) \(M\)
\(c_2\) \(c_3\) \(\dots\) \(c_{N-1}\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(\vdots\)
\(a_M\) \(b_M\)

Output Format

Output the minimum total cost of installing the "Resting Spots" to satisfy the conditions. If it is impossible to satisfy the conditions, output -1.

Sample Input and Output

Sample Input #1

7 7
-1 100 10 1 -1
1 2
2 3
3 6
2 4
4 5
5 6
6 7

Sample Output #1

101

Sample Input #2

4 3
-1 -1
1 2
2 3
3 4

Sample Output #2

-1

Notes/Hints

Constraints

• \(3 \leq N \leq 500\)
• \(N-1 \leq M \leq 1000\)
• \(-1 \leq c_i \leq 10^9 \ (2 \leq i \leq N-1)\)
• If \(c_i = -1\), scene \(i\) is a "Battle" scene.
• If \(c_i \geq 0\), scene \(i\) is a "Field" scene, and the cost to install a "Resting Spot" there is \(c_i\).
• \(1 \leq a_i, b_i \leq N \ (1 \leq i \leq M)\)
• Indicates that there is a passageway from scene \(a_i\) to scene \(b_i\).
• When viewed as a directed graph with \(N\) vertices and \(M\) edges, there exists a path from vertex \(1\) to all other vertices and a path from all vertices to vertex \(N\). There are no cycles.
• All input values are integers.

Sample Explanation 1

Choosing scenes \(3\) and \(5\) is optimal.

Sample Explanation 2

It is impossible to install a "Resting Spot" between scenes \(2\) and \(3\).

见题面 Input 部分

见题面 Output 部分