Час гри
Вася купив нову комп'ютерну гру. При проходженні гри потрібно викпонати декілька місій. Якою саме буде наступна місія, повністю визначається результатом проходження попередньої. Для кожної місії існує єдина послідовність місій, які потрібно пройти від початку гри, щоб потрапити у задану місію.
Так як Вася — справжній "геймер", то він вирішив не просто пройти гру від початку і до кінця одного з можливих завершень, а пройти усі місії гри. Для цього йому приходиться після досягнення кінця гри починати гру заново і, починаючи з деякої місії, йдти по тим гілкам сюжету, по яким він не ходиі раніше.
Всього у грі N місій, пронумерованих числами від 1 до N. Гра починається з місії номер 1. Кожна місія займе у Васі T_i хвилин, навіть якщо він проходив її у одному з попередні запусків гри. Допоможіть Васі підрахувати, яку мінімальну кількість хвилин він потратить на те, щоб пройти усі місії у грі.
Вхідні дані
У першому рядку вхідних даних знаходиться ціле число N (1 ≤ N ≤ 100). У другому рядкуе через пропуск записано інформацію про час проходження кожної місії (1 ≤ T_i ≤ 100) по порядку (1 ≤ i ≤ N). У третьому рядку записано ціле число M = (N – 1) — кількість переходів між місіями. Час переходу між місіями і час перезапуску гри вважати рівними нулю. У кожному з наступних M рядків записано по два числа — F і T, які означають, що у місію T можна потрапити, лише виконавши місію F. Усі значення T різні.
Вихідні дані
Виведіть мінімальну кількість часу, який потрібно Васі для того, щоб пройти усі місії гри.