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