H. Заправки

В стране $n$ городов, соединённых дорогами. Проезд по одной дороге тратит ровно один бак бензина. Кроме бака есть канистра той же вместимости — ровно на одну заправку бака.

В городе $i$ бак стоит $c_i$. В каждом городе можно: заправить бак, заправить бак и канистру сразу, или перелить бензин из канистры в бак — переливание бесплатно. Доберитесь из города 1 в город $n$, потратив как можно меньше денег.

Первая строка содержит число $n$ ($1 \le n \le 100$).

Вторая строка — $n$ чисел $c_i$ ($0 \le c_i \le 100$).

Третья строка — число дорог $M$, далее $M$ строк с парами городов. Дороги двусторонние, между парой городов не более одной дороги, петель нет.

Одно число — наименьшая суммарная стоимость или $-1$.