There are N cities in the country, some of which are connected by roads. It takes one tank of gasoline to drive on one road. In addition, you have a gas canister that holds the same amount of fuel as a gas tank.
In each city, a tank of gasoline has a different cost. You need to get from the first city to the Nth one, spending as little money as possible.
In each city, you can fill up the tank, fill the tank and the canister, or pour gasoline from the canister into the tank. This allows you to save money by buying gasoline in those cities where it is cheaper, but the canister is only enough for one tank filling!
Input
The first line contains the number N (1<=N<=100), the next line contains N numbers, the i-th of which sets the cost of gasoline in the i-th city (all these are integers from the range from 0 to 100 ). Then comes the number M – the number of roads in the country, followed by a description of the roads themselves. Each road is given by two numbers – the numbers of the cities it connects. All roads are two-way (that is, they can be driven both in one direction and in the other direction), there is always no more than one road between two cities, there are no roads leading from the city to itself.
Output
Required to output a single number – the total cost of the route, or -1 if it's impossible to get there.
Examples
| # |
Input |
Output |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |