국가에는 N개의 도시가 있으며 그 중 일부는 도로로 연결되어 있습니다. 한 도로를 주행하려면 휘발유 한 탱크가 필요합니다. 또한 가스 탱크와 동일한 양의 연료를 담을 수 있는 가스통이 있습니다.
도시마다 휘발유 탱크의 비용이 다릅니다. 가능한 한 적은 비용으로 첫 번째 도시에서 N 번째 도시로 이동해야 합니다.
각 도시에서 탱크를 채우거나, 탱크와 캐니스터를 채우거나, 캐니스터에서 탱크로 휘발유를 부을 수 있습니다. 이를 통해 더 저렴한 도시에서 휘발유를 구입하여 돈을 절약할 수 있지만 용기는 탱크를 한 번 채우는 데만 충분합니다!
입력
첫 번째 줄에는 숫자 N(1<=N<=100)이 포함되어 있고, 다음 줄에는 N개의 숫자가 포함되어 있으며, 그 중 i번째 줄은 i번째 도시의 휘발유 가격을 설정합니다. 0에서 100까지의 범위). 그런 다음 숫자 M이 나옵니다. 해당 국가의 도로 수, 도로 자체에 대한 설명. 각 도로는 두 개의 숫자로 표시됩니다. 그것이 연결하는 도시의 수. 모든 도로는 양방향입니다(즉, 한 방향과 다른 방향으로 모두 운전할 수 있음). 두 도시 사이에는 항상 하나 이상의 도로가 없으며 도시에서 자체로 이어지는 도로는 없습니다.
출력
단일 숫자 출력에 필요 – 경로의 총 비용 또는 해당 경로에 도달할 수 없는 경우 -1입니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
<사업부>4
1 10 2 15
<사업부>4
<디브>1 2
1 3
4 2
4 3
|
2 |