Задача №1737. Заправки
В стране \(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
2