Maximum Achievement Path

A game consists of n levels. Each level i provides an achievement value of a_i upon completion. There are m pairs of levels that are mutually unlocked, meaning that passing level u unlocks level v and vice‐versa. The levels form a connected graph satisfying m ≤ n (in fact, the graph is either a tree (if m = n − 1) or a unicyclic graph (if m = n)).

Kate wishes to play the game in a linear fashion. She chooses any starting level, and after completing a level c, she can only move next to levels that are directly adjacent (i.e. have a mutual unlocking relation with c). Moreover, each level can be played at most once.

The goal is to choose a valid path (a simple path in the graph) so that the total achievement (the sum of a_i along the path) is maximized.

Note on formulas: Use LaTeX formatting for formulas. For example, the numbers of levels and relations satisfy $m\le n$, and if Kate follows levels $i_1,i_2,\dots,i_k$, then the total achievement is $\sum_{j=1}^{k}a_{i_j}$.

inputFormat

The first line contains two integers n and m ($1\leq n\leq 10^5$, m = n-1 or m = n).

The second line contains n integers: a₁, a₂, \dots, a_n (each |a_i| ≤ 10⁹), representing the achievement values.

The next m lines each contains two integers u and v ($1\leq u,v\leq n$) indicating there is a mutual unlocking relation between levels u and v.

outputFormat

Output a single integer, the maximum total achievement that Kate can obtain by following a valid path.

sample

5 4
1 2 -1 3 -2
1 2
2 3
2 4
4 5

6