Dungeion 3

　

You are a famous adventurer and have already conquered two dungeons. You have obtained a map of a new dungeon with several passages and treasure chests on it. The map shows the value of the treasures in each treasury.

You can enter the dungeon from any of the treasuries and escape the dungeon from any of the treasuries. During the time between entering and exiting, you can move several times through the passages between the treasuries to get the treasures of the treasuries you visited. According to the map, each passage can go in both directions, and you can reach any treasure house from any treasure house via one or more passages. However, once a passage is traversed, the second and subsequent passages can only be traversed in the same direction as the first. Treasures in the treasury can only be obtained the first time you visit it. At this time, we want to maximize the total value of the treasures we obtain.

Given the information on the map, write a program to find the maximum value of the sum of the values of the treasures that can be obtained from the time of entry to the time of escape. Assume that the treasuries are assigned numbers from 1 to $N$.

Input

The input is given in the following form.

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

In the first line, the number of treasuries $N$ ($2 \leq N \leq 10^5$) and the number of passages $M$ ($1 \leq M \leq 2 \times 10^5$) are given. In the following $N$ lines, the value $v_i$ ($1 \leq v_i \leq 1000$) of the treasure placed in the $i$-th treasury is given. In the following $M$ lines, the numbers $s_i$,$t_i$ ($1 \leq s_i,t_i \leq N,s_i \ne t_i$) of the treasure vaults connected to the two ends of each passage are given. No passage connecting the same treasury can be given more than once.

Output

Output the maximum value of the sum of the values of the treasures that can be obtained in a line.

Sample Input and Output

Sample Input

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

Sample Output

14

---