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>

// #include <iostream> // cout, endl, cin
// #include <string> // string, to_string, stoi
// #include <vector> // vector
// #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
// #include <utility> // pair, make_pair
// #include <tuple> // tuple, make_tuple
// #include <cstdint> // int64_t, int*_t
// #include <cstdio> // printf
// #include <map> // map
// #include <queue> // queue, priority_queue
// #include <set> // set
// #include <stack> // stack
// #include <deque> // deque
// #include <unordered_map> // unordered_map
// #include <unordered_set> // unordered_set
// #include <bitset> // bitset
// #include <climits>
// #include <cmath>
// #include <iomanip>
// #include <functional>
// #include <numeric>
// #include <random>
 
using namespace std;

#define int long long
#define pb push_back
#define eb emplace_back
// #define F first
// #define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end())
#define Double double
// #define endl '\n'
 
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>; 
using ll = long long;
using ld = long double;
using UnWeightedGraph = vector<vector<int>>;
ll INF = LLONG_MAX / 4 - 100;
int IINF = INT_MAX / 4;
ll mod = 1e9 + 7;
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
 
long double pi = 3.141592653589793238;
    
class fact {
public:
    long long fmod = 1e9+7;
    vector<long long> fac, finv, inv;
    fact (int n, long long Mod = 1e9+7) {
        fmod = Mod;
        fac = vector<long long>(n + 1, 0);
        finv = vector<long long>(n + 1, 0);
        inv = vector<long long>(n + 1, 0);
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1; 
        for (int i = 2; i < n + 1; i++) {
            fac[i] = fac[i-1] * i % fmod;
            inv[i] = mod - inv[mod%i] * (mod/i) % mod;
            finv[i] = finv[i-1] * inv[i] % mod;
        }
    }
    ll nCr(ll n, ll r) {if(n < r) return 0; return fac[n] * finv[r] % fmod * finv[n-r] % fmod;}
    ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%fmod;}a = a * a%fmod; b >>= 1;}return c;}
    inline int operator [] (int i) {return fac[i];}
    ll DeBuG(ll n, ll r);
};
    
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return (a / GCD(a, b)) * (b / GCD(a, b)) * GCD(a, b);}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%mod;}a = a * a%mod; b >>= 1;}return c;}
ld POW(ld a, ll b) {ld c = 1; while (b > 0) {if (b & 1) {c = a * c;}a = a * a; b >>= 1;}return c;}
void PRI(ll n) {bool a[n + 1]; for (int i = 0; i < n + 1; i++) {a[i] = 1;}for (int i = 2; i < n + 1; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}
bool isSqrt(ll a) {return pow(sqrt(a),2) == a ? 1 : 0;}
void YesNo(bool a) {if (a) cout << "Yes"; else cout << "No"; cout << endl;}
void yesno(bool a) {if (a) cout << "yes"; else cout << "no"; cout << endl;}
void YESNO(bool a) {if (a) cout << "YES"; else cout << "NO"; cout << endl;}
double dis(int x1, int x2, int y1, int y2) {
    return sqrt((double)abs(x1-x2)*(double)abs(x1-x2)+(double)abs(y1-y2)*(double)abs(y1-y2));
}
int ceili(int x, int y) {
    if (x % y == 0) return x / y;
    else return x / y + 1;
}
unsigned int randxor() {
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
 
uint64_t xor64(void) {
    static uint64_t x = 88172645463325252ULL;
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
}

vector<int> v, V;
vector<int> g[100005];
vector<int> t[100005];
vector<int> low, ord, comp;
vector<pair<int, int>> bridge;
int ans = 0;

int cnt = 0;
int dfs(int u, int par) {
    if (ord[u] != -1) return low[u];
    low[u] = ord[u] = cnt++;
    for (auto &&to : g[u]) {
        if (to == par) continue;
        chmin(low[u], dfs(to, u));
        if (ord[u] < low[to]) bridge.push_back({u, to});
    }
    return low[u];
}

void dfs(int u, int par, int &k) {
    if (~par && ord[par] >= low[u]) comp[u] = comp[par];
    else comp[u] = k++;
    for (auto& to : g[u]) {
        if (comp[to] == -1) dfs(to, u, k);
    }
}

int dfs2(int u, int par) {
    vector<int> res;
    for (auto to : t[u]) {
        if (to == par) continue;
        res.pb(dfs2(to, u));
    }
    sort(rall(res));
    if (res.size() == 0) {
        chmax(ans, V[u]);
        return V[u];
    }
    if (res.size() == 1) {
        chmax(ans, res[0] + V[u]);
        return res[0] + V[u];
    }
    chmax(ans, res[0] + res[1] + V[u]);
    return res[0] + V[u];
}

void solve() {
    int n, m; cin >> n >> m;
    v.resize(n), low.resize(n, INF), ord.resize(n, -1), comp.resize(n, -1);
    rep (i, n) cin >> v[i];
    rep (_, m) {
        int s, t; cin >> s >> t; s--, t--;
        g[s].pb(t), g[t].pb(s);
    }
    int k = 0;
    dfs(0, -1);
    dfs(0, -1, k);

    for (auto& e : bridge) {
        int x = comp[e.first], y = comp[e.second];
        t[x].pb(y);
        t[y].pb(x);
    }

    V.resize(k);
    rep (i, n) V[comp[i]] += v[i];

    dfs2(0, -1);

    cout << ans << endl;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}