#P4410. [HNOI2009] 无归岛

    ID: 3341 远端评测题 1000ms 125MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>2009各省省选湖南动态规划dp仙人掌

[HNOI2009] 无归岛

题目描述

Neverland 是个神奇的地方,它由一些岛屿环形排列组成,每个岛上都生活着之中与众不同的物种。

但是这些物种都有一个共同的生活习性:对于同一个岛上的任意两个生物,他们有且仅有一个公共朋友,即对同一岛上的任意两个生物 a 和 b 有且仅有一个生物 c 既是 a 的朋友也是 b 的朋友,当然某些岛上也可能会只有一个生物孤单地生活着。

这一习性有一个明显的好处,当两个生物发生矛盾的时候,他们可以请那个唯一的公共朋友来裁决谁对谁错。 另外,岛与岛之间也有交流,具体来说,每个岛都会挑选出一个最聪明的生物做代表,然后这个生物与他相邻的两个岛的代表成为朋友。

不幸运的是,A 世界准备入侵 Neverland,作为 Neverland 的守护者,Lostmonkey 想知道在一种比较坏的情况下 Neverland 的战斗力。因为和朋友并肩作战,能力会得到提升,所以 Lostmonkey 想知道在不选出一对朋友的情况下Neverland的最大战斗力。即选出一些生物,且没有一对生物是朋友,并且要求它们的战斗力之和最大。

输入格式

第一行包含用空格隔开的两个整数 nnmm,分别表示 Neverland 的生物种数和朋友对数。

接下来的 mm 行描述所有朋友对,具体来说,每行包含用空格隔开的两个整数 aabb,表示生物 aa 和生物 bb 是朋友(每对朋友只出现一次)。第 m+2m+2 行包含用空格隔开的 nn 个整数,其中第 ii 个整数表示生物 ii 的战斗力 AiA_i

输出格式

仅包含一个整数,表示满足条件的最大战斗力。

6 7
1 2
2 3
3 4
4 1
3 6
3 5
5 6
20 10 30 15 20 10
50

提示

【样例说明】

有四个岛,生物 1111 号岛,生物 2222 号岛,生物 33556633 号岛,生物 4444 号岛。

输入数据保证 4n1000004≤n≤1000001a,bn1 \le a,b \le n1m2000001 \le m \le 2000001000Ai1000-1000 \le A_i \le 1000