题目描述

有 $n$ 座城镇和 $m$ 条双向普通道路，城镇从 $1$ 到 $n$ 编号。普通道路网连通，城镇 $i$ 有 $p_i$ 名居民，指挥中心位于城镇 $1$。

在水灾发生前，你可以建设零条、一条或两条加固应急通道。每条应急通道连接两座不同的城镇，可以与普通道路连接相同的一对城镇；两条应急通道的端点对也可以相同。应急通道是双向的，且不会被水灾摧毁。

应急通道建成后，如果 $m>0$，对手会在知道你建设的所有应急通道后，选择并摧毁恰好一条普通道路。此后，其余普通道路和所有应急通道均可通行。

一次水灾后的可达人口，是仍能从城镇 $1$ 到达的所有城镇的人口之和。一个建设方案的价值，是对手选择普通道路后可达人口的最小值。若 $m=0$，则不发生道路摧毁，建设方案的价值定义为总人口。你需要求出所有建设方案价值的最大值。

平行的普通道路是不同的道路，对手每次只摧毁其中一条，其余平行道路仍可通行。若删除一条普通道路后，普通道路网不再连通，则称这条道路为桥。

输入格式

从文件 double.in 中读取数据。

第一行输入两个整数 $n,m$，分别表示城镇数和普通道路数。

第二行输入 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示各城镇的人口。

接下来 $m$ 行，第 $i$ 行输入两个整数 $u_i,v_i$，表示第 $i$ 条普通道路连接城镇 $u_i$ 与 $v_i$。

输出格式

输出到文件 double.out 中。

输出一个整数，表示能够保证的最大可达人口。

样例

1 0
7

7

5 4
3 1 4 1 5
1 2
2 3
3 4
4 5

14

6 5
10 1 2 3 4 5
1 2
1 3
1 4
1 5
1 6

24

5 6
3 4 5 6 7
1 2
1 2
2 3
3 4
4 2
4 5

25

样例解释

样例 #1 中没有普通道路，也无法建设连接两座不同城镇的应急通道，唯一城镇始终可达。

样例 #2 中，在城镇 $1$ 与城镇 $5$ 之间建设一条应急通道后，任意一条普通道路被摧毁都不会使城镇失去与城镇 $1$ 的联系。

样例 #3 中，每条连接两座叶子城镇的应急通道最多能同时保护两条普通道路。两条通道可以保护人口分别为 $2,3,4,5$ 的四座叶子城镇，使人口为 $1$ 的城镇成为最坏情况下唯一失去联系的城镇，因此答案为 $25-1=24$。两条通道不可能同时保护五条普通道路。

样例 #4 中，两条连接城镇 $1,2$ 的普通道路互为备用，城镇 $2,3,4$ 之间的道路也形成了环。再建设一条连接城镇 $1,5$ 的应急通道后，摧毁任意一条普通道路都不会减少可达人口。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 200000$，$0\le m\le 400000$；
• $1\le p_i\le 10^9$（$1\le i\le n$）；
• $1\le u_i,v_i\le n$ 且 $u_i\ne v_i$（$1\le i\le m$）；
• 普通道路允许平行边，不含自环；
• 当 $n=1$ 时 $m=0$；当 $n>1$ 时 $n-1\le m$，且普通道路网连通。

人口总和、答案以及计算过程中出现的人口之和都可能超过 $32$ 位有符号整数的表示范围。

若原图没有桥，则任意一条普通道路被摧毁后仍然连通，答案为总人口。单个城镇也按此约定处理。

本题采用子任务捆绑计分：只有通过一个子任务中的全部测试点，才能获得该子任务的分数。

子任务编号	分值	额外约束
$1$	$10$	$n\le 2000$
$2$	$20$	普通道路网是一棵树；保证至少存在一个最优方案只建设零条或一条应急通道
$3$	$25$	保证至少存在一个最优方案只建设零条或一条应急通道
$4$	$45$	无特殊限制

大样例下载