Задача C. Заправки

Автор:Зимние сборы 2005   Ограничение времени:2 сек
Входной файл:filling.in   Ограничение памяти:64 Мб
Выходной файл:filling.out  

Условие

В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.

При этом есть еще канистра для бензина, куда входит столько же бензина, сколько входит в бак. В каждом городе можно заправить бак, залить бензин в канистру, залить и туда и туда, или же перелить бензин из канистры в бак.

Формат входного файла

Во входном файле записано сначала число N, затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все это целые числа из диапазона от 0 до 100). Затем идет число M — количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

Формат выходного файла

В выходной файл выведите одно число — суммарную стоимость маршрута или &1, если добраться невозможно.

Ограничения

1 ≤ N ≤ 100

Примеры тестов

Входной файл (filling.in) Выходной файл (filling.out)
1
4
1 10 2 15
4
1 2 1 3 4 2 4 3
2
2
4
1 10 2 15
0
-1

0.112s 0.011s 13