Description

At the Battle of Red Cliffs, Huang Gai (Huang Gai) pretended to defect to Cao Cao’s fleet with ships loaded with reeds and oil.

Under Pang Tong’s “chained ships” stratagem, Cao Cao’s warships were connected by iron chains. No two ships were at the same position, and no chains intersected one another or passed through any ship. Each ship had a given strategic value.

To ensure the destructive effect, Huang Gai must guarantee that every pair among the ignited Cao Cao ships is directly connected by an iron chain. He hopes to find a plan to ignite ships whose total value is as large as possible.

Input Format

The first line contains numbers $N$, $M$, the number of warships and the number of iron chains.

The next $N$ lines, the $i$-th line contains $1$ number $V_i$, the strategic value of the $i$-th warship.

The next $M$ lines, the $i$-th line contains $2$ numbers $S_i$, $T_i$, indicating the two ships connected by an iron chain.

It is guaranteed that this is a valid fleet arrangement.

Output Format

Output one number, the maximum total value of warships that can be destroyed.

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

8100

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

4500

Hint

• Constraints
  • For $50\%$ of the testdata, $N$, $M \le 10$.
  • For $100\%$ of the testdata, $N \le 450$, $M \le 900$, $V_i \le 6000$.
• Note
  • Every sentence in the statement (except the first paragraph) is relevant.

Translated by ChatGPT 5