Gold Bandits

Time limit5sMemory limit256 MB

Summary

The bandits rob the richest set of villages along a shortest road from home to the castle that still leaves a return route avoiding robbed villages.

Level: Hard8 of 10
Topics: Shortest path, Graph
Solved: No attempts yet

Problem

A valley in a distant land holds many villages. A cruel king rules them all and demands that every village pay him tribute in gold each year. When the king demands it, a village must carry the gold to his castle as quickly as it can.

One village in the kingdom is a village of bandits. The bandits saved no gold for the king, because they spent every bit of gold they had. They are bandits, though. On the way to the castle they can rob any village they pass through and hand that gold to the king as their own. For each village on the way they choose whether to rob it.

The bandits pass through as few villages as possible on the way to the castle, so their route to the castle uses the fewest roads. They have one more concern. After delivering the gold they must be able to get home, and they consider it unsafe to return through a village they robbed. They do not care how long the way home is, and they may travel the same road more than once.

Find the largest total amount of gold the bandits can rob on the way to the king's castle while still being able to get home safely.

Input

The input holds several test cases. Each test case begins with a line holding two integers $n$ and $m$ ( $3 \le n \le 36$ , $n-1 \le m \le n(n-1)/2$ ), where $n$ is the number of villages and $m$ is the number of roads. The villages are numbered $1$ through $n$ . Village $1$ is the bandits' home and village $2$ holds the king's castle.

The next line holds $n-2$ space separated integers $g$ ( $1 \le g \le 5000$ ), the amount of gold in villages $3, 4, \dots, n$ in that order. The bandits' home and the king's castle are left out of this list and hold no gold.

Each of the next $m$ lines holds two integers $a$ and $b$ ( $1 \le a < b \le n$ ), meaning that a road connects village $a$ and village $b$ . Every road is two way. The $m$ pairs $(a, b)$ are all different. Every village is reachable from every other village, directly or through other villages.

The input ends with a line holding two zeros.

Output

For each test case, print one integer on its own line: the largest total amount of gold the bandits can rob and still get home safely. Print no blank lines between the answers.

Examples3

Example 1

Input

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

Expected output

Example 2

Input

8 9
2500 4000 1 1 1 1
1 3
3 4
2 4
1 5
5 6
4 6
3 7
7 8
2 8
0 0

Expected output

Example 3

Input

6 7
100 5000 4950 1
1 3
3 4
3 5
2 4
2 5
1 6
4 6
0 0

Expected output