Competitions

# 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 (1n100) 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 (its 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
1 10 2 15
4
1 2 1 3 4 2 4 3

Output example #1
3

Input example #2
4
1 10 2 15
0

Output example #2
-1


Example description: In the first example of an optimal solution - from the 1 st of the city to go to third, and then in the 4 th. Fuel will have to buy at 1 and 3 cities