ICPC (Ibaraki Committee of Physical Competitions)의 일원으로서 Tsukuba 시에서 열리는 마라톤 행사의 경로를 계획하는 일을 맡았다. 초보자부터 전문가까지 많은 주자가 참가할 예정이다.

행사에 적합한 모든 도로 구간과 그 위의 모든 교차로가 표시된 도시 지도가 있다. 경주는 Tsukuba High 앞 교차로에서 시작하고 City Hall 앞 교차로에서 끝난다. 두 교차로 모두 지도에 표시되어 있다.

실력이 다양한 주자들의 혼잡과 혼란을 피하기 위해 경로는 같은 교차로를 두 번 방문해서는 안 된다. 따라서 도로 구간은 어느 방향으로나 사용할 수 있지만 경로에 최대 한 번만 포함할 수 있다. 행사의 주된 목적은 시민의 여가와 건강 증진이므로 기록은 중요하지 않고 경로의 거리는 자유롭게 정할 수 있다.

경로의 모든 교차로에는 일정 수의 인력을 배치해야 한다. 이 교차로들과 인접한 교차로, 즉 경로상의 교차로와 도로 구간 하나로 직접 연결된 교차로에도 일반 교통이 경주를 방해하지 않도록 인력을 배치해야 한다. 한 교차로가 경로 위에 있을 때와 경로에 인접할 때 필요한 인력 수는 같지만, 교차로마다 크기와 모양에 따라 필요한 인력 수가 다르며 그 수도 지도에 표시되어 있다.

시 당국은 이런 행사의 인건비를 포함한 비용을 줄이고자 한다. 필요한 총 인력 수를 최소화하는 경로를 계획하고 그 수를 출력하는 프로그램을 작성하라.

입력

입력은 다음 형식의 간략한 도시 지도를 나타내는 하나의 테스트 케이스로 이루어진다.

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

첫 줄에는 두 양의 정수 $n$, $m$이 주어진다. $n$은 지도의 교차로 수 ($2 \le n \le 40$), $m$은 인접한 교차로를 연결하는 도로 구간 수이다. 교차로는 $1$부터 $n$까지의 정수로 구분된다.

그다음 $n$개 줄은 필요한 인력 수를 나타낸다. 이 중 $k$번째 줄의 정수 $c_k$ ($1 \le c_k \le 100$)는 교차로 $k$에 필요한 인력 수이다.

나머지 $m$개 줄은 교차로 사이의 도로 구간 목록이다. 각 줄에는 교차로 $i_k$, $j_k$를 연결하는 구간을 나타내는 두 정수 $i_k$, $j_k$ ($i_k \ne j_k$)가 주어진다. 같은 교차로 쌍을 연결하는 도로 구간은 최대 하나이다.

경주는 교차로 $1$에서 시작하여 교차로 $n$에서 끝난다. 시작과 도착 교차로를 연결하는 경로가 하나 이상 존재함이 보장된다.

출력

필요한 인력 수의 최솟값을 나타내는 정수를 출력하라.

그림 I.1. 예제 입력 1의 최소 비용 경로

그림 I.1은 예제 입력 1의 최소 비용 경로를 보여 준다. 화살표는 경로를 나타내며 회색 원은 인력을 배치해야 하는 교차로이다. 이 경우 필요한 최소 인력 수는 $17$이다.

예제

입력 1

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2

출력 1

17