Вася купил новую компьютерную игру. При прохождении
игры нужно выполнить несколько миссий. Какой именно будет следующая миссия,
полностью определяется результатом прохождения предыдущей. Для каждой миссии
существует единственная последовательность миссий, которые нужно пройти от
начала игры, чтобы попасть в заданную миссию.
Так как Вася — настоящий «геймер», то он решил не
просто пройти игру от начала и до одной из возможных концовок, а пройти все
миссии игры. Для этого ему приходится после достижения конца игры начинать игру
заново и, начиная с некоторой миссии, идти по тем веткам сюжета, по которым он
не ходил ранее.
Всего в игре N миссий,
занумерованных числами от 1 до N. Игра начинается с миссии
номер 1. Каждая миссия займёт у Васи Ti минут,
даже если он проходил её в одном из предыдущих запусков игры. Помогите Васе
подсчитать, какое минимальное количество минут он потратит на то, чтобы пройти
все миссии в игре.
В первой строке входных данных находится целое число N
(1 £ N £ 100). Во второй строке через пробел записана
информация о времени прохождения каждой миссий (1 £ Ti £ 100) по
порядку (1 £ i £ N). В третьей строке записано
целое число M = (N – 1)
— количество переходов между миссиями. Время перехода между миссиями и время перезапуска
игры считать равными нулю. В каждой из последующих M строк
записано по два числа — F и T, значащие, что в миссию T
можно попасть, только выполнив миссию F.
Все значения T различны.
Выведите минимальное количество времени, которое
потребуется Васе для того, чтобы пройти все миссии игры.
|
Пример ввода 1
2
2
5
1
1
2
Пример вывода 1
7
|
Пример ввода 2
3
1
2 5
2
1
2
1
3
Пример вывода 2
9
|
