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