1372 - ダンジョン３

問題文

あなたは有名な冒険家であり、すでに２つのダンジョンを制覇した。あなたはいくつかの通路と宝物庫が記された新たなダンジョンの地図を入手した。地図にはそれぞれの宝物庫にある財宝の価値が書かれている。

あなたは、任意の宝物庫からダンジョンに侵入し、任意の宝物庫からダンジョンを脱出することができる。侵入から脱出までの間に、通路を通って宝物庫の間を何度か移動して、訪れた宝物庫の財宝を手に入れることができる。地図によれば、各通路は双方向に通ることができ、どの宝物庫からどの宝物庫にも１本以上の通路を経由してたどりつくことができる。しかし、通路は一度通ると二度目以降は一度目と同じ向きにしか通ることができなくなる。宝物庫の財宝は、そこを最初に訪れたときだけ手に入れることができる。このとき、手にする財宝の価値の総和を最大にしたい。

地図の情報が与えられたとき、侵入から脱出までの間に手にいれることのできる財宝の価値の総和の最大値を求めるプログラムを作成せよ。ただし、宝物庫には1からNまでの番号が割り当てられているものとする。

入力

入力は以下の形式で与えられる。

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

１行目に宝物庫の数$N$ ($2 \leq N \leq 10^5$)と通路の数$M$ ($1 \leq M \leq 2 \times 10^5$)が与えられる。続く$N$行に、$i$番目の宝物庫に置かれている財宝の価値$v_i$ ($1 \leq v_i \leq 1000$)が与えられる。続く$M$行に、それぞれの通路の両端に接続されている宝物庫の番号$s_i$,$t_i$ ($1 \leq s_i,t_i \leq N, s_i \ne t_i$)が与えられる。ただし、同じ宝物庫同士をつなぐ通路は２度以上与えられない。

出力

得ることができる財宝の価値の総和の最大値を１行に出力する。

入出力例

入力例

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

出力例

14