eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Заправки

Заправки

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У країні n міст, деякі з яких з'єднані між собою дорогами. Для того, щоб проїхати по одній дорозі потрібно один бак бензину. У кожному місті бак бензину має різну віртість. Вам потрібно дістатись з першого міста у n-те, витративши якомога меншу кількість грошей.

Вхідні дані

Спочатку йде кількість міст n~(1 \le n \le 100), потім йде n чисел, i-те з яких задає вартість бензину в i-ому місті (всі числа цілі з діапазону від 0 до 100). Потім йде кількість доріг m в країні, далі йде опис самих доріг. Кожна дорога задається двома числами — номерами міст, які вона з'єднує. Всі дороги двосторонні (тобто по ним можна їздити як в одну, так і в іншу сторону); між двома містами завжди існує не більше однієї дороги; не існує доріг, які ведуть з міста в себе.

Вихідні дані

Виведіть одно число — сумарну вартість маршруту або -1, якщо дістатись неможливо.

Приклад

Вхідні дані #1
4
1 10 2 15
4
1 2 1 3 4 2 4 3
Вихідні дані #1
3
Вхідні дані #2
4
1 10 2 15
0
Вихідні дані #2
-1