마라톤 경로 정하기

이바라키 체육대회 위원회 위원인 당신은 츠쿠바시에서 열리는 마라톤 대회의 경로를 짠다. 초보자부터 상급자까지 아주 많은 주자가 참가한다.

손에는 대회에 쓸 수 있는 도로 구간과 그 구간 위의 교차로가 모두 적힌 시내 지도가 있다. 경기는 츠쿠바 고등학교 앞 교차로에서 출발해 시청 앞 교차로에서 끝나며, 두 곳 모두 지도에 표시되어 있다.

실력 차가 큰 주자들이 한곳에 몰려 뒤엉키지 않도록 경로는 같은 교차로를 두 번 지나지 않는다. 도로 구간은 어느 방향으로든 달릴 수 있지만 경로에는 많아야 한 번 들어간다. 대회의 목적은 시민의 여가와 건강 증진이므로 기록은 중요하지 않고 경로의 길이는 마음대로 정해도 된다.

경로 위의 모든 교차로에 진행 요원을 배치한다. 경로 위 교차로와 도로 구간으로 바로 이어진 교차로에도 일반 통행이 경기를 방해하지 않도록 요원을 배치한다. 교차로 $k$에 필요한 요원 수 $c_k$는 그 교차로가 경로 위에 있을 때와 경로 위 교차로와 이웃할 때가 같다. 교차로마다 크기와 모양에 따라 필요한 인원이 다르며 그 수도 지도에 적혀 있다. 한 교차로에 요원을 두 번 배치하지는 않는다.

시 당국은 이런 행사의 인건비를 줄이려 한다. 필요한 요원 수가 가장 적은 경로를 찾아 그 요원 수를 출력하는 프로그램을 작성하라.

입력은 시내 지도를 요약한 테스트 케이스 하나로 이루어지며, 형식은 다음과 같다.

n m
c1
.
.
.
cn
i1 j1
.
.
.
im jm

첫 줄에는 양의 정수 $n$과 $m$이 있다. $n$은 지도에 있는 교차로 수이고 ($2 \le n \le 40$), $m$은 이웃한 교차로를 잇는 도로 구간 수다. 교차로에는 $1$번부터 $n$번까지 번호가 붙는다.

이어지는 $n$개 줄에는 필요한 요원 수가 있다. 그중 $k$번째 줄의 정수 $c_k$는 교차로 $k$에 필요한 요원 수다 ($1 \le c_k \le 100$).

남은 $m$개 줄에는 교차로를 잇는 도로 구간이 있다. 각 줄의 두 정수 $i_k$와 $j_k$는 교차로 $i_k$와 $j_k$를 잇는 구간을 뜻한다 ($i_k \ne j_k$). 같은 교차로 쌍을 잇는 구간은 많아야 하나다.

경기는 $1$번 교차로에서 출발해 $n$번 교차로에서 끝난다. 출발 교차로와 도착 교차로를 잇는 경로가 적어도 하나 있음이 보장된다.

필요한 요원 수의 최솟값을 정수 하나로 출력한다.

위 그림은 첫 번째 예제 입력에서 요원 수가 가장 적은 경로다. 화살표가 경로이고, 회색으로 칠한 원이 요원을 배치하는 교차로다. 이때 필요한 요원은 17명이다.