赤壁之战
题目描述
赤壁之战,黄盖率舰满载薪草膏油诈降曹军。
受庞统所授的连环计,曹军战船之间由铁索相连,没有两艘战船在同一位置,也没有铁索两两相交或穿过战船。每艘船都有其一定的战略价值。
为了保证达到破坏效果,黄盖需要保证被点燃的曹军船只两两之间都有铁索连接。他希望找到一种方案点燃总价值尽可能大的战船。
输入输出格式
输入格式
第一行包含数字 $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$。
#### 【注意】
题目中的每句话(除了第一段)都有作用。