Game Time#2104
Vasya has purchased a new computer game. To progress in the game, he needs to complete several missions, and each mission is only unlocked by completing a specific previous mission. For each mission, there is a unique sequence of missions that leads from the beginning of the game to that mission.
Being a dedicated gamer, Vasya wants to complete not just one playthrough, but every mission in the game. To do this, after reaching an end, he must restart the game and take unexplored branches to complete all distinct missions.
There are missions in total, numbered from to . The game starts with mission number . Each mission takes T_i minutes to complete, even if Vasya already completed it in a previous playthrough.
Calculate the minimum time Vasya needs to complete all missions in the game.
The first line contains an integer (1 \leq N \leq 100).
The second line contains the times for each mission, T_i (1 \leq T_i \leq 100), in order (1 \leq i \leq N).
The third line contains an integer M = N - 1, the number of transitions between missions.
The following lines each contain two integers and , indicating that mission can only be visited after completing mission . All values are distinct.
The time between missions and game restart time are considered zero.
Output the minimum time Vasya needs to complete all the missions in the game.
Example
4
1 2 3 4
3
1 2
1 3
3 414Example
2
2 4
1
1 26Example 1