Problem Description

Rabbits love money.

A rabbit has decided to stroll through a certain city. However, due to time constraints, it cannot visit the same town twice, but it can start from any town.

Town $i$ has $D_i$ yen, and the rabbit wants to collect as much money as possible.

Determine the maximum amount of money that can be collected.

There are $N$ towns and $K$ roads. Road $i$ connects town $X_i$ and town $Y_i$. Roads can be traversed in both directions.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ D_1 $ $ D_2 $ : $ D_N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ : : $ X_K $ $ Y_K $

• The first line contains integers $N$ and $K$.
• The next $N$ lines contain the amount of money $D_i$ in town $i$.
• The following $K$ lines contain $X_i$ and $Y_i$.

Output Format

Output the maximum amount of money the rabbit can collect in one line to the standard output.

Note that the answer may not fit into a 32-bit integer.

Sample Input and Output

Sample Input #1

6 6
1
2
3
4
5
7
1 2
1 3
1 6
2 4
3 4
4 5

Sample Output #1

20

Sample Input #2

4 2
1
10
5
6
1 2
3 4

Sample Output #2

11

Sample Input #3

5 4
2
3
5
6
7
1 3
1 4
2 4
4 5

Sample Output #3

20

Notes/Hints

Constraints

• $1 \leq N \leq 50$
• $1 \leq K \leq 50$
• $1 \leq D_i \leq 1,000,000,000$
• $1 \leq X_i, Y_i \leq N$
• $X_i \neq Y_i$
• It is guaranteed that there are no duplicate roads.
• The number of possible stroll routes is at most $2,000,000$.

Partial Points

This problem has partial points.

If you correctly solve all test cases where $1 \leq N, K \leq 10$, you will be awarded 50 points.

If you correctly solve all remaining test cases, you will be awarded another 50 points.

Sample Explanation 1

Starting from town $6$ and going in the order $6 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 5$, you can collect $7 + 1 + 3 + 4 + 5 = 20$ yen.

见题面 Input 部分

见题面 Output 部分