Час гри#2104
Вася придбав нову комп'ютерну гру. Щоб просунутися у грі, йому потрібно виконати декілька місій, і кожна місія відкривається лише після проходження певної попередньої місії. Для кожної місії існує унікальна послідовність місій, яка веде від початку гри до цієї місії.
Будучи відданим геймером, Вася хоче пройти не лише один раз, а виконати всі місії у грі. Для цього, дійшовши до кінця, він повинен перезапустити гру й обрати ще не досліджені гілки, щоб виконати всі різні місії.
Всього у грі місій, пронумерованих від до . Гра починається з місії номер . На проходження кожної місії потрібно T_i хвилин, навіть якщо Вася вже проходив її в одному з попередніх проходжень.
Обчисліть мінімальний час, необхідний Васі, щоб виконати всі місії у грі.
Перший рядок містить одне ціле число (1 \leq N \leq 100).
Другий рядок містить часи на проходження кожної місії, T_i (1 \leq T_i \leq 100), у порядку (1 \leq i \leq N).
Третій рядок містить одне ціле число M = N-1 — кількість переходів між місіями.
Наступні рядків містять по два цілих числа і , що вказують: щоб виконати місію , спершу потрібно виконати місію . Всі значення різні.
Час між місіями та на перезапуск гри вважається рівним нулю.
Виведіть мінімальний час, необхідний Васі для виконання всіх місій у грі.
Приклад 1