Existem N cidades no país, algumas das quais ligadas por estradas. Leva um tanque de gasolina para dirigir em uma estrada. Em cada cidade, um tanque de gasolina tem um custo diferente. Você precisa ir da primeira cidade à enésima gastando o mínimo de dinheiro possível. Você não pode comprar gasolina para uso futuro.
A primeira linha contém o número N (1≤N≤100), a próxima linha contém N números, o i-ésimo dos quais especifica o custo da gasolina na i-ésima cidade (estes são números inteiros de 0 a 100 ). Em seguida, vem o número M – o número de estradas no país, seguido de uma descrição das próprias estradas. Cada estrada é dada por dois números – os números das cidades que ele conecta. Todas as estradas são de mão dupla (ou seja, podem ser percorridas em uma direção e na outra), sempre não há mais do que uma estrada entre duas cidades, não há estradas que levem da cidade a ela mesma.
Saída
Necessário para gerar um único número – o custo total da rota ou -1 se for impossível chegar lá.
Exemplos
| # |
Entrada |
Saída |
| 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 |