Problem Description

In the Battle of Red Cliffs, Huang Gai led a fleet loaded with kindling and oil to feign surrender to Cao Cao's army.

Following Pang Tong's strategy of chaining ships together, the ships of Cao Cao's army were connected by iron chains. No two ships were in the same position, and no chains intersected or passed through the ships. Each ship had a certain strategic value.

To ensure the destruction effect, Huang Gai needed to ensure that the ships he set on fire were all connected by chains. He hoped to find a way to ignite the ships with the largest total strategic value.

Input Format

The first line contains two numbers $N$ and $M$, representing the number of ships and the number of chains, respectively.

The next $N$ lines each contain one number $V_i$, representing the strategic value of the $i$-th ship.

The next $M$ lines each contain two numbers $S_i$ and $T_i$, representing the two ships connected by the $i$-th chain.

The data guarantees a feasible fleet arrangement.

Output Format

Output a single number, representing the maximum total strategic value of the ships that can be destroyed.

Sample Input and Output

Input Sample #1

4 6
100
5000
1000
2000
1 2
1 3
1 4
2 3
2 4
3 4

Output Sample #1

8100

Input Sample #2

6 8
1500
1000
100
2000
500
300
1 2
1 3
1 4
2 4
3 5
4 5
4 6
5 6

Output Sample #2

4500

Notes

Data Scale

For $50\%$ of the data, $N$ and $M$ are guaranteed to be less than or equal to $10$.

For $100\%$ of the data, $N$ is guaranteed to be less than or equal to $450$, $M$ is guaranteed to be less than or equal to $900$, and $V_i$ is guaranteed to be less than or equal to $6000$.

Attention

Every sentence in the problem (except the first paragraph) serves a purpose.

见题面 Input 部分

见题面 Output 部分