Em cada cidade, você pode encher o tanque, encher o tanque e o botijão ou despejar a gasolina do botijão no tanque. Isso permite que você economize comprando gasolina nas cidades onde é mais barato, mas o botijão só dá para encher um tanque!
A primeira linha contém o número N (1<=N<=100), a linha seguinte contém N números, o i-ésimo dos quais define o custo da gasolina na i-ésima cidade (todos são números inteiros de intervalo 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 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |