#P2128. 赤壁之战

赤壁之战

题目描述

赤壁之战,黄盖率舰满载薪草膏油诈降曹军。

受庞统所授的连环计,曹军战船之间由铁索相连,没有两艘战船在同一位置,也没有铁索两两相交或穿过战船。每艘船都有其一定的战略价值。

为了保证达到破坏效果,黄盖需要保证被点燃的曹军船只两两之间都有铁索连接。他希望找到一种方案点燃总价值尽可能大的战船。

输入格式

第一行包含数字 NNMM ,表示战船的数量和铁索的数量。

接下来包含 NN 行,每 ii 行包含 11 个数字 ViV_i,表示第 ii 艘战船的战略价值。

接下来包含 MM 行,每 ii 行包含 22 个数字 SiS_iTiT_i ,表示铁索连接的两艘船只。

数据保证这是一个可行的舰队安排。

输出格式

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

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

提示

【数据规模】

对于 50%50\% 的数据,保证 NNM10M \le 10

对于 100%100\% 数据,保证 N450N \le 450M900M \le 900Vi6000V_i \le 6000

【注意】

题目中的每句话(除了第一段)都有作用。