赤壁之战

题目描述

赤壁之战,黄盖率舰满载薪草膏油诈降曹军。 受庞统所授的连环计,曹军战船之间由铁索相连,没有两艘战船在同一位置,也没有铁索两两相交或穿过战船。每艘船都有其一定的战略价值。 为了保证达到破坏效果,黄盖需要保证被点燃的曹军船只两两之间都有铁索连接。他希望找到一种方案点燃总价值尽可能大的战船。

输入输出格式

输入格式


第一行包含数字 $N$,$M$ ,表示战船的数量和铁索的数量。 接下来包含 $N$ 行,每 $i$ 行包含 $1$ 个数字 $V_i$,表示第 $i$ 艘战船的战略价值。 接下来包含 $M$ 行,每 $i$ 行包含 $2$ 个数字 $S_i$,$T_i$ ,表示铁索连接的两艘船只。 数据保证这是一个可行的舰队安排。

输出格式


输出一个数字,表示最多摧毁总价值多少的战船。

输入输出样例

输入样例 #1

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

输出样例 #1

8100

输入样例 #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

输出样例 #2

4500

说明

#### 【数据规模】 对于 $50\%$ 的数据,保证 $N$,$M \le 10$。 对于 $100\%$ 数据,保证 $N \le 450$,$M \le 900$,$V_i \le 6000$。 #### 【注意】 题目中的每句话(除了第一段)都有作用。