Problem: Escape

An undirected graph with positive values ​​at the vertices is given. The vertices are numbered from 1 to N, and the i-th vertex has a value of w_i. You can start from the first vertex and move on the graph with the constraint that you cannot pass the edge that you just passed. At each vertex, you can get the score of the value that the vertex has only when you visit it for the first time.

Find the maximum sum of the points you can get.

Constraints

* 1 ≤ N ≤ 100000
* N − 1 ≤ M ≤ 100000
* 1 ≤ w_i ≤ 1000
* 1 ≤ u_i, v_i ≤ N
* There are no multiple edges or self edges
* The graph is concatenated



Input Format

Input is given from standard input in the following format.


N M
w_1 w_2 ... w_N
u_1 v_1
u_2 v_2
...
u_M v_M


In the first line, the number of vertices N of the graph and the integer M representing the number of edges are entered.
The value w_i of each vertex is entered in the second line.
In addition, the number of the two vertices connected by each side is entered in the M line.


Output Format

Print the answer on one line.

Sample Input 1


6 6
1 2 3 4 5 6
1 2
twenty three
3 4
14
4 5
5 6


Sample Output 1


twenty one


<image>
You can collect the points of all vertices by going from vertices 1 → 2 → 3 → 4 → 5 → 6.

Sample Input 2


7 8
1 3 3 5 2 2 3
1 2
twenty three
3 1
14
1 7
1 5
1 6
5 6


Sample Output 2


16


<image>
You can collect 16 points by going from vertices 1 → 2 → 3 → 1 → 5 → 6 → 1 → 4.





Example

Input

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


Output

21

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100000

struct Info{
	Info(){
		node_id = pre_node = sum_value = 0;
	}

	Info(int arg_node_id,int arg_pre_node,int arg_sum_value){
		node_id = arg_node_id;
		pre_node = arg_pre_node;
		sum_value = arg_sum_value;
	}
	bool operator<(const struct Info &arg) const{ //★総価値の降順(PQ)★
		return sum_value < arg.sum_value;
	}

	int node_id,pre_node,sum_value;
};

int N,M;
int root;
int value[NUM],in_num[NUM],max_value[NUM];
bool is_cicle[NUM];
vector<int> G[NUM];

/*
 * 木なら葉がある→入次数が1のノードがある!!
 * 葉を刈ったら葉になるノードは、木の一部で非サイクル経路
 */


int main(){

	scanf("%d %d",&N,&M);

	for(int i = 0; i < N; i++)scanf("%d",&value[i]);

	for(int i = 0; i < N; i++)in_num[i] = 0;

	root = 0;
	int from,to;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d",&from,&to);
		from--;
		to--;
		G[from].push_back(to);
		G[to].push_back(from);
		in_num[from]++;
		in_num[to]++;
	}

	for(int i = 0; i < N; i++)is_cicle[i] = true;

	//非サイクル部分を計算
	queue<int> CALC;
	for(int i = 1; i < N; i++){
		if(in_num[i] == 1){
			is_cicle[i] = false;
			CALC.push(i);
		}
	}

	int node_id;
	int next_node,next_value;

	while(!CALC.empty()){
		node_id = CALC.front();
		CALC.pop();

		for(int i = 0; i < G[node_id].size(); i++){
			next_node = G[node_id][i];
			if(is_cicle[next_node] == false || next_node == root)continue; //既に葉と認定されているならSKIP

			in_num[next_node]--;
			if(in_num[next_node] == 1){ //ボトムアップ的（再帰的）に、木の経路上にあるノードを特定する
				is_cicle[next_node] = false;
				CALC.push(next_node);
			}
		}
	}

	int ans = value[root];
	for(int i = 1; i < N; i++){
		if(is_cicle[i]){ //サイクル経路上のノードなら、全て訪問可能
			ans += value[i];
		}
	}

	int maximum = 0;
	for(int i = 0; i < N; i++)max_value[i] = 0; //★★木上の頂点は、元来たノードに戻れないとの制約のため、事実上の有向路となるので、到達時の最大コストで切る★★

	//始点(rootから行き来できるサイクル中のどれか)をPQに突っ込む
	priority_queue<Info> Q;
	for(int i = 0; i < N; i++){
		if(!is_cicle[i])continue; //サイクル上の点でなければSKIP

		for(int k = 0; k < G[i].size(); k++){
			next_node = G[i][k];
			if(is_cicle[next_node])continue; //行先がサイクル上の点ならSKIP

			next_value = value[next_node];
			if(max_value[next_node] < next_value){ //最大値で遷移する場合のみpush
				max_value[next_node] = next_value;
				Q.push(Info(next_node,i,next_value));
			}
		}
	}

	Info info;
	while(!Q.empty()){

		//★★降順かつ、値の増えるループなので、先にpopしておく★★
		info = Q.top();
		Q.pop();

		maximum = max(maximum,info.sum_value);

		if(info.sum_value < max_value[info.node_id]){
			continue;
		}else{
			for(int i = 0; i < G[info.node_id].size(); i++){
				next_node = G[info.node_id][i];
				if(next_node == info.pre_node || is_cicle[next_node] == true)continue;
				next_value = info.sum_value+value[next_node];

				if(max_value[next_node] < next_value){
					max_value[next_node] = next_value;
					Q.push(Info(next_node,info.node_id,next_value));
				}
			}
		}
	}

	printf("%d\n",ans+maximum);

	return 0;
}