P16179 [ICPC 2014 NAIPC] Gold Bandits

在遥远山峦的一个山谷里，分布着许多村庄。所有村庄都由一位残暴的国王统治，他要求每个村庄每年向他进贡黄金。当国王下令时，村庄必须尽快将黄金送到国王那里。 王国中有一个强盗村庄。这个强盗村庄没有为国王积攒任何黄金，因为他们把每一分钱都花光了！他们该怎么办呢？嗯，由于他们是强盗，当他们在前往城堡的途中经过其他村庄时，他们可以选择（或不选择）从路径上的任何村庄偷走黄金，并将其作为自己的贡品献给国王。 强盗们会以尽可能少的村庄数量到达城堡。他们还有另一个考虑因素——在将黄金交给国王后，强盗们必须能够返回家园。他们认为，如果返回途中经过一个他们偷过黄金的村庄，那是不安全的。除此之外，强盗们不关心返回家园需要多长时间。 请确定强盗们在前往国王城堡的路上能够偷取的最大黄金数量，同时仍能安全返回家园。

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

对于每个测试用例，输出一个整数，表示强盗们能够偷取并仍能安全回家的最大黄金数量。每个整数输出在自己的行上，不要包含空格。输出之间不要打印空行。

翻译由 DeepSeek V3.2 完成