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 <bits/stdc++.h>
#define int long long
using namespace std;

struct Edge {
	int from, to;
	Edge(int f, int t) : from(f), to(t) {}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;

pair<vector<int>, Edges> bridge(const Graph& g) {
	const int n = g.size();
	int idx = 0, s = 0, t = 0, k = 0;
	vector<int>ord(n, -1), onS(n), stk(n), roots(n), cmp(n);
	Edges brdg;
	function<void(int, int)> dfs = [&](int v, int u) {
		ord[v] = idx++;
		stk[s++] = v;
		onS[v] = true;
		roots[t++] = v;
		for (auto& e : g[v]) {
			int w = e.to;
			if (ord[w] == -1)dfs(w, v);
			else if (u != w && onS[w])
				while (ord[roots[t - 1]]>ord[w])--t;
		}
		if (v == roots[t - 1]) {
			brdg.emplace_back(u, v);
			while (true) {
				int w = stk[--s];
				onS[w] = false;
				cmp[w] = k;
				if (v == w)break;
			}
			--t;
			++k;
		}
	};
	for (int u = 0; u<n; ++u) {
		if (ord[u] == -1) {
			dfs(u, n);
			brdg.pop_back();
		}
	}
	return make_pair(cmp, brdg);
}

class HLDecomposition {
	vector<vector<int>> g;
	vector<int> vid, head, heavy, parent, depth, inv;
	int dfs(int curr, int prev) {
		parent[curr] = prev;
		int sub = 1, max_sub = 0;
		for (int next : g[curr]) if (next != prev) {
			depth[next] = depth[curr] + 1;
			int sub_next = dfs(next, curr);
			sub += sub_next;
			if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
		}
		return sub;
	}
	void bfs() {
		int k = 0;
		queue<int> q({ 0 });
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				inv[vid[i]] = i;
				head[i] = h;
				for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
			}
		}
	}
public:
	HLDecomposition(int n)
		: g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}

	void add(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	void build() {
		dfs(0, -1);
		bfs();
	}
	void for_each(int u, int v, function<void(int, int)> f) {
		if (vid[u] > vid[v]) swap(u, v);
		f(max(vid[head[v]], vid[u]), vid[v]);
		if (head[u] != head[v]) for_each(u, parent[head[v]], f);
	}
};

template <typename T>
class LazySegmentTree {
	const int n;
	const T flag;
	const T id;
	vector<T> data, data2;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	T sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return id;
		if (l <= lb && ub <= r) return data[node] != flag ? data[node] : data2[node] * (ub - lb);
		if (data[node] == flag) {
			return data2[node] * (min(r, ub) - max(l, lb));
		}
		return sub(l, r, node * 2, lb, (lb + ub) / 2) + sub(l, r, node * 2 + 1, (lb + ub) / 2, ub);
	}
	void suc(int l, int r, int node, int lb, int ub, T val) {
		if (ub <= l || r <= lb) return;
		if (l <= lb && ub <= r) {
			data[node] = flag;
			data2[node] = val;
			return;
		}
		int left = node * 2, right = node * 2 + 1;
		if (data[node] == flag) {
			data[left] = data[right] = flag;
			data2[left] = data2[right] = data2[node];
		}
		int c = (lb + ub) / 2;
		suc(l, r, left, lb, c, val);
		suc(l, r, right, c, ub, val);
		data[node] = (data[left] == flag ? data2[left] * (c - lb) : data[left]) + (data[right] == flag ? data2[right] * (ub - c) : data[right]);
	}
public:
	LazySegmentTree(int n_, T flag_) :
		n(size(n_)), flag(flag_), id(0), data(n * 2, id), data2(n * 2) {}
	void update(int l, int r, T val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	T find(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

signed main()
{
	cin.sync_with_stdio(false);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<int> w(N);
	for (int i = 0; i < N; i++) {
		cin >> w[i];
	}
	Graph G(N);
	vector<int> u(M), v(M);
	for (int i = 0; i < M; i++) {
		cin >> u[i] >> v[i]; u[i]--; v[i]--;
		G[u[i]].emplace_back(u[i], v[i]);
		G[v[i]].emplace_back(v[i], u[i]);
	}
	auto br = bridge(G);
	int V = 0;
	for (int i = 0; i < N; i++) {
		V = max(V, br.first[i] + 1);
	}
	HLDecomposition hl(V);
	for (int i = 0; i < M; i++) {
		if (br.first[u[i]] != br.first[v[i]]) {
			hl.add(br.first[u[i]], br.first[v[i]]);
		}
	}
	hl.build();
	LazySegmentTree<int> st(V, -1);
	for (int i = 0; i < N; i++) {
		hl.for_each(br.first[i], br.first[i], [&](int l, int r) {
			st.update(l, r, st.find(l, r) + w[i]);
		});
	}
	vector<int> ko(V);
	for (int i = 0; i < N; i++) {
		ko[br.first[i]]++;
	}
	int res = 0;
	for (int i = 0; i < V; i++) {
		if (ko[i] > 1) {
			hl.for_each(br.first[0], i, [&](int l, int r) {
				res += st.find(l, r);
				st.update(l, r, 0);
			});
		}
	}
	int add = 0;
	for (int i = 0; i < V; i++) {
		int tmp = 0;
		hl.for_each(br.first[0], i, [&](int l, int r) {
			tmp += st.find(l, r);
		});
		add = max(add, tmp);
	}
	cout << res + add << endl;
	return 0;
}