Problem: You are a famous adventurer and have already won two dungeons. You got a new dungeon map with some walkways and a treasure trove. The map shows the value of the treasure in each treasure chest.

You can enter the dungeon from any treasure chest and escape the dungeon from any treasure chest. From invasion to escape, you can navigate through the passages between the treasure chests several times to get the treasures of the treasure chest you visited. According to the map, each passage can be bidirectional, and any treasure trove can be reached from any treasure trove via one or more passages. However, once the passage is passed, it can only be passed in the same direction as the first time after the second time. Treasure in the treasure chest can only be obtained the first time you visit it. At this time, I want to maximize the total value of the treasures I get.

Create a program that finds the maximum sum of the treasure values ​​that can be obtained between invasion and escape when given map information. However, it is assumed that the treasure house is assigned a number from 1 to N.



input

The input is given in the following format.


$ N $ $ M $
$ v_1 $
$ v_2 $
::
$ v_N $
$ s_1 $ $ t_1 $
$ s_2 $ $ t_2 $
::
$ s_M $ $ t_M $


The first line gives the number of treasure trove $ N $ ($ 2 \ leq N \ leq 10 ^ 5 $) and the number of passages $ M $ ($ 1 \ leq M \ leq 2 \ times 10 ^ 5 $). The following $ N $ line is given the value of the treasure in the $ i $ th treasure trove $ v_i $ ($ 1 \ leq v_i \ leq 1000 $). The following $ M $ line is given the treasure trove numbers $ s_i $, $ t_i $ ($ 1 \ leq s_i, t_i \ leq N, s_i \ net_i $) connected to both ends of each aisle. However, the passage connecting the same treasure chests cannot be given more than once.

output

The maximum value of the total value of the treasure that can be obtained is output in one line.

Examples

Input

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


Output

14


Input

None


Output

None

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define NUM 100005

struct Edge{
	Edge(){
		s = t = 0;
	}
	Edge(int arg_s,int arg_t,ll arg_cost){
		s = arg_s;
		t = arg_t;
	}
	bool operator<(const struct Edge &arg) const{
		if(s != arg.s){
			return s < arg.s;
		}else{
			return t < arg.t;
		}
	}
	int s,t;
};

struct Info{
	Info(int arg_to,int arg_edge_id,int arg_port = -1){
		to = arg_to;
		edge_id = arg_edge_id;
		port = arg_port;
	}
	int to,edge_id,port;
};

struct Data{
	Data(int arg_node_id,int arg_depth){
		node_id = arg_node_id;
		depth = arg_depth;
	}
	bool operator<(const struct Data &arg) const{
		return depth < arg.depth;
	}

	int node_id,depth;
};


int V,E,number;
int value[NUM];
int order[NUM],lowlink[NUM];
int height[NUM],parent[NUM],connector[NUM];
int sum_value[NUM];
int depth_table[NUM],PARENT[NUM],max_value[NUM];
bool visited[NUM],is_bridge[NUM];
Edge edge[2*NUM];
vector<Info> G[NUM],Group_G[NUM];

int find(int x){
	if(x == parent[x])return x;
	else{
		return parent[x] = find(parent[x]);
	}
}

bool isSame(int x,int y){
	return find(x) == find(y);
}

void unite(int x,int y){
	x = find(x);
	y = find(y);

	if(x == y)return;

	if(height[x] < height[y]){
		parent[x] = y;
	}else{
		parent[y] = x;
		if(height[x] == height[y])height[x]++;
	}
}

void recursive(int node_id){

	order[node_id] = number++;
	lowlink[node_id] = order[node_id];

	int next_node;

	for(int i = 0; i < G[node_id].size(); i++){
		next_node = G[node_id][i].to;

		if(order[next_node] == -1){ //頂点next_nodeをまだ訪れていない

			visited[G[node_id][i].edge_id] = true;
			recursive(next_node);
			lowlink[node_id] = min(lowlink[node_id],lowlink[next_node]);

		}else if(visited[G[node_id][i].edge_id] == false){ //後退辺をまだ通っていない場合
			lowlink[node_id] = min(lowlink[node_id],order[next_node]);
		}
	}
}

//深さを計算&親子関係の構築
void calcDepth(int group_id,int depth,int parent_id){
	depth_table[group_id] = depth;
	PARENT[group_id] = parent_id;
	for(int i = 0; i < Group_G[group_id].size(); i++){
		if(Group_G[group_id][i].to == parent_id)continue;
		calcDepth(Group_G[group_id][i].to,depth+1,group_id);
	}
}


int main(){

	scanf("%d %d",&V,&E);

	for(int i = 0; i < V; i++){

		scanf("%d",&value[i]);
	}

	for(int i = 0; i < E; i++){
		scanf("%d %d",&edge[i].s,&edge[i].t);

		edge[i].s--;
		edge[i].t--;

		if(edge[i].s > edge[i].t){
			swap(edge[i].s,edge[i].t);
		}

		G[edge[i].s].push_back(Info(edge[i].t,i));
		G[edge[i].t].push_back(Info(edge[i].s,i));
	}

	sort(edge,edge+E);

	number = 0;

	for(int i = 0; i < V; i++){
		order[i] = -1;
		lowlink[i] = -1;
	}

	//★dfsで通らなかった辺が後退辺!!★
	for(int i = 0; i < E; i++){
		visited[i] = false;
	}

	recursive(0);

	int from,to;

	for(int i = 0; i < E; i++){

		is_bridge[i] = false;
	}

	int num_bridge = 0;

	for(int i = 0; i < E; i++){

		from = edge[i].s;
		to = edge[i].t;

		if(order[edge[i].s] > order[edge[i].t]){
			swap(from,to);
		}

		if(order[from] < lowlink[to]){
			num_bridge++;
			is_bridge[i] = true;
		}
	}

	for(int i = 0; i < V; i++){

		parent[i] = i;
		height[i] = 0;
	}

	//union-findでグループ分け
	for(int i = 0; i < E; i++){
		if(is_bridge[i]){
			continue;
		}

		unite(edge[i].s,edge[i].t);
	}

	//グループごとの価値の合計
	for(int i = 0; i < V; i++){

		sum_value[i] = 0;
	}
	for(int i = 0; i < V; i++){

		sum_value[find(i)] += value[i];
	}

	//グループ間のエッジを張る(すべて橋のはず)
	for(int i = 0; i < E; i++){

		if(isSame(edge[i].s,edge[i].t)){
			continue;
		}

		Group_G[find(edge[i].s)].push_back(Info(find(edge[i].t),i));
		Group_G[find(edge[i].t)].push_back(Info(find(edge[i].s),i));
	}

	/*木の直径を求める*/

	for(int i = 0; i < V; i++){

		depth_table[i] = -1;
		max_value[i] = 0;
	}

	for(int i = 0; i < V; i++){

		if(i == find(i)){

			calcDepth(i,0,-1);
			break;
		}
	}

	priority_queue<Data> Q;

	//深さ順に、最も遠い子との距離を計算<★直径は、かならず[ある頂点]からの(最大)2個の[子方向の最大点]の和であるはず★>
	for(int i = 0; i < V; i++){
		if(depth_table[i] == -1)continue;

		Q.push(Data(i,depth_table[i]));
	}

	int ans = 0;
	int max1,max2;

	while(!Q.empty()){

		max1 = 0,max2 = 0; //ノードから延びる最大の2辺のコストを抽出

		//node_idから延びる点を走査
		for(int i = 0; i < Group_G[Q.top().node_id].size(); i++){
			if(Group_G[Q.top().node_id][i].to == PARENT[Q.top().node_id])continue; //親方向には走査しない

			if(max1 < max_value[Group_G[Q.top().node_id][i].to] + sum_value[Group_G[Q.top().node_id][i].to]){ //子のノードの総価値と、子のノードからの最長点までの価値の和
				max2 = max1;
				max1 = max_value[Group_G[Q.top().node_id][i].to] + sum_value[Group_G[Q.top().node_id][i].to];
			}else if(max2 < max_value[Group_G[Q.top().node_id][i].to] + sum_value[Group_G[Q.top().node_id][i].to]){
				max2 = max_value[Group_G[Q.top().node_id][i].to] + sum_value[Group_G[Q.top().node_id][i].to];
			}
		}

		ans = max(ans,max1+max2+sum_value[Q.top().node_id]);
		max_value[Q.top().node_id] = max1;
		Q.pop();
	}

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

	return 0;
}