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 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. You can’t buy gasoline for future use.
Input
The first line contains the number N (1≤N≤100), the next line contains N numbers, the i-th of which specifies the cost of gasoline in the i-th city (these are integers 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 |
5
3 6 1 7 6
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
|
3 |