# Petrol Stations

There are $n$ cities, some of which are connected by roads. In order to drive along one road you need one tank of gasoline. In each city the petrol tank has a different cost. You need to get out of the first city and reach the $n$-th one, spending the minimum possible amount of money.

## Input

Starts with the number $n(1≤n≤100)$ of cities, followed by $n$ numbers, $i$-th of which gives the cost of gasoline in the $i$-th city (all numbers are integers in the range from $0$ to $100$). Then the number $m$ of roads in the country is given. It is followed by the description of roads. Each road is defined by two numbers — the numbers of cities it connects. All roads are two-way (it's possible to travel in both directions). There is always no more than one road between the two cities. There is no road from the city to itself.

## Output

Print the total cost of the route, or $−1$ if it is impossible to reach the $n$-th city.