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\le n\le 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.

Examples