황금 도적단

먼 나라의 산속 골짜기에 마을이 여럿 있다. 마을을 다스리는 왕은 잔인해서 해마다 각 마을에 금을 공물로 바치라고 요구한다. 왕이 공물을 요구하면 마을은 되도록 빨리 금을 성으로 가져가야 한다.

이 왕국에는 도적 마을이 하나 있다. 도적들은 왕에게 바칠 금을 한 푼도 모아 두지 않았다. 가진 금을 전부 써 버렸기 때문이다. 그래도 도적은 도적이다. 성으로 가는 길에 지나는 마을에서 금을 빼앗아 자기 것인 양 왕에게 바칠 수 있다. 지나는 마을마다 빼앗을지 말지는 도적들이 고른다.

도적들은 성까지 가면서 지나는 마을 수를 최소로 한다. 즉 성으로 가는 경로는 지나는 길의 수가 가장 적은 경로다. 조건이 하나 더 있다. 금을 바친 뒤에는 집으로 돌아올 수 있어야 하는데, 금을 빼앗은 마을을 지나 돌아오는 것은 위험하다고 본다. 돌아오는 길이 얼마나 긴지는 신경 쓰지 않고, 같은 길을 여러 번 지나도 된다.

집까지 안전하게 돌아올 수 있으면서 성으로 가는 길에 빼앗을 수 있는 금의 최대 합을 구하라.

입력은 테스트 케이스 여러 개로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$과 $m$이 주어진다 ($3 \le n \le 36$, $n-1 \le m \le n(n-1)/2$). $n$은 마을 수, $m$은 길의 수다. 마을 번호는 $1$부터 $n$까지다. 마을 $1$은 도적들의 집이고, 마을 $2$에는 왕의 성이 있다.

다음 줄에는 마을 $3, 4, \dots, n$이 차례로 가진 금의 양 $g$가 공백으로 구분되어 $n-2$개 주어진다 ($1 \le g \le 5000$). 도적들의 집과 왕의 성은 이 목록에서 빠져 있고, 금이 없다.

이어지는 $m$개의 줄에는 정수 $a$와 $b$가 주어지며 ($1 \le a < b \le n$), 마을 $a$와 마을 $b$를 잇는 길이 있다는 뜻이다. 모든 길은 양방향이다. $m$개의 쌍 $(a, b)$는 서로 다르다. 어느 마을에서 어느 마을로든 직접 또는 다른 마을을 거쳐 갈 수 있다.

입력의 마지막 줄에는 $0$이 두 개 주어진다.

각 테스트 케이스마다 도적들이 빼앗고도 집까지 안전하게 돌아올 수 있는 금의 최대 합을 한 줄에 정수 하나로 출력한다. 답 사이에 빈 줄을 넣지 않는다.