В країні \(N\) міст, деякі з них з'єднані між собою дорогами. Для того, щоб проїхати однією дорогою потрібен один бак бензину. В кожному місті бак бензину має різну вартість. Вам необхідно дістатись з міста номер \(1\) до міста номер \(N\), витративши якомога менше грошей. Купляти бензуну більше ніж вміщує бак не можна.

Формат вхідних даних

В першому рядку ціле число \(N\) (\(1 \le N \le 100\))
В наступному рядку \(N\) цілих чисел \(Ai\)- вартість бензину в кожному з міст. (\(0 \le Ai \le 100\)).
В наступному рядку ціле число \(M\) - кількість доріг в країні.
Далі йде опис доріг. Кожна дорога задається двома числами - номерами міст які вона з'єднує. Всі дороги двосторонні. Між двома містами існує не більше однієї дороги, і не існує доріг які ведуть з міста в самого себе.

Формат вихідних даних

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

Приклад вхідних даних-1

5
3 6 1 7 6 
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1

Приклад вихідних даних-1

3

Приклад вхідних даних-2

5
3 7 2 9 4
4
1 2
1 3
2 3
4 5

Приклад вихідних даних-2

-1