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

Вхідні дані

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

Вихідні дані

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