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