学校有许多景点，景点间有路相连，构成了一幅无向连通偶度图。现在，我们要求一条参观路线，当然得能够回到起点，使得每条路和每个景点都至少被访问 111 次。每到一个曾经还没有到过的景点，同学们就能够得到相应的愉悦值，不过愉悦值是会发生变化的，如果一个景点它是第 kkk 个被新到达的，那么这个景点能给同学们的愉悦值就会减少 kkk，下次再到这个景点时不得到任何愉悦值。当然同学们不愿意多走路，所以每走一条路（重复走的也算），同学们就会得到一个 −1-1−1 的愉悦值。我们希望通过参观能使同学们尽量高兴，即得到的总愉悦值最大。
不过还要特别说明的是：nnn 个景点被编号为 1∼n1\sim n1∼n；参观路线起点是 111 号景点；可能有某条路它两头连接着同一个景点，两个景点间也可能有多条路相连。
输入数据包含由回车符分割的多组测试数据（测试数据不超过 555 组），对于每组数据：
第一行两个整数 n, m（1≤n≤200, 1≤m≤800)n,\ m（1 \leq n \leq 200,\ 1\leq m \leq 800)n, m（1≤n≤200, 1≤m≤800)，表示景点数和道路的数目。
接下来 nnn 行，每行一个整数，表示每个景点初始能够给同学们的愉悦值 wi(1≤wi≤103)w_i(1 \leq w_i \leq 10^3)wi(1≤wi≤103)。
接着 mmm 行，每行两个整数，分别为每条路所连接的两个景点的编号。
对于每组数据，输出一行，每行是一个整数，表示最大的愉悦值。
6 7 1 7 4 10 20 5 2 4 1 5 2 1 4 5 3 6 1 6 1 3
19
