Game Time
Vasya has purchased a new computer game that requires completing several missions. Each mission's availability depends on the outcome of the previous one, forming a unique sequence from the start of the game to each mission.
Being a dedicated gamer, Vasya aims not only to reach one of the game's possible endings but to complete every mission available. To achieve this, he must restart the game after reaching an ending and explore any storyline branches he hasn't yet completed.
The game consists of N missions, numbered from 1 to N, with the game beginning at mission number 1. Each mission takes T_i minutes to complete, regardless of whether Vasya has finished it in a previous playthrough. Your task is to help Vasya determine the minimum time required to complete all missions in the game.
Input
The first line of input provides an integer N (1 ≤ N ≤ 100), representing the number of missions. The second line lists the time required for each mission (1 ≤ T_i ≤ 100) in sequence (1 ≤ i ≤ N). The third line contains an integer M = (N – 1), indicating the number of transitions between missions. Transition times between missions and the time to restart the game are considered zero. Each of the following M lines contains two numbers, F and T, indicating that mission T can only be accessed after completing mission F. All T values are unique.
Output
Output the minimum time Vasya needs to complete all the missions in the game.