在遥远国度的山丘中，有一个拥有许多村庄的山谷。这些村庄都由一位残暴的国王统治，他每年要求每个村庄向他进贡黄金。当国王下令时，村庄必须尽快将黄金送到国王手中。

王国里有一个强盗村。强盗村没有为国王存下任何黄金，因为他们把所有的黄金都花光了！他们该怎么办呢？好吧，既然他们是强盗，当他们穿过其他村庄前往城堡时，他们可以选择（也可以不选择）从路径上的任何村庄偷取黄金，并将其作为自己的贡品献给国王。

强盗们前往城堡时会尽可能少地经过村庄。他们还有另一个考虑因素——在将黄金交给国王后，强盗们必须能够安全返回家中。他们认为，如果返回途中经过了被他们偷过黄金的村庄，那是很不安全的。除此之外，强盗们并不关心返回家中需要多长时间。

请确定强盗在前往国王城堡的路上最多能偷取多少黄金，并确保他们能够安全返回家中。

输入格式

输入包含多组测试数据。每组测试数据的第一行包含两个整数 $n$ ($3 \le n \le 36$) 和 $m$ ($n-1 \le m \le n(n-1)/2$)，其中 $n$ 是村庄的数量，$m$ 是道路的数量。村庄编号为 $1 \dots n$。村庄 $1$ 是强盗的家，村庄 $2$ 是国王的城堡。下一行包含 $n-2$ 个以空格分隔的整数 $g$ ($1 \le g \le 5,000$)，分别表示村庄 $3, 4, \dots, n$ 中的黄金数量（跳过了强盗的家和国王的城堡）。接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示村庄 $a$ 和 $b$ 之间有一条道路。所有道路都是双向的。所有 $m$ 对 $(a, b)$ 都是唯一的。从任意村庄到其他任何村庄都存在直接或间接的路径。输入以一行两个 $0$ 结束。

输出格式

对于每组测试数据，输出一个整数，表示强盗在能够安全返回家中的前提下，最多能偷取的黄金数量。每个整数占一行，不要包含空格。输出之间不要打印任何空行。

样例

输入 1

3 3
1
1 2
2 3
1 3
4 4
24 10
1 3
2 3
2 4
1 4
6 8
100 500 300 75
1 3
1 4
3 6
4 5
3 5
4 6
2 5
2 6
7 7
90 1000 700 2000 800
1 3
1 4
1 5
3 7
5 6
2 6
3 6
0 0

输出 1

0
24
800
700