Maximum Lost Harmony

In the city of pigsty, there are n communities (numbered from 1 to n) interconnected by m undirected roads. Each community i has a harmony value \(H_i\). Several years later, after iPig rebuilt the city by demolishing all the old roads and constructing m new ones, he ensured that every community lies in at most one cycle (i.e. every vertex is contained in at most one simple cycle).

However, a group of anti-harmony activists have devised a plan to brainwash the communities. Their plan is as follows: they choose an arbitrary set \(T\) of communities to attack. For every community in \(T\), a pig is sent to that community, setting its harmony value to zero. Additionally, for every community directly adjacent (i.e. connected by a road) to any community in \(T\), a pig is also sent to guard it, and its harmony value is reset to zero. In order to avoid confusion (such as having two pigs in one community), they ensure that every community receives at most one pig. Hence, the final effect is that every community in the set \[ T \cup \{ j\mid \exists i\in T \text{ such that } (i,j)\in E \} \] has its harmony value set to zero.

iPig is worried and wonders: in the worst-case scenario, how much harmony value will be lost?

Mathematically, for a chosen set \(T\), the lost harmony value is \[ \text{LostHarmony}(T)=\sum_{v\in T \cup \{j:\exists i\in T \text{ and } (i,j)\in E\}} H_v. \] The adversaries can choose any set \(T\). Note that if the city has at least one road (i.e. if a component has more than one vertex) it is always possible to choose a set \(T\) (for example, an independent dominating set) whose closed neighborhood is the entire set of communities in that component. For isolated communities (with no connecting roads), one must choose the community itself to cover it. In all cases, the adversaries can cover every community. Therefore, the maximum lost harmony value is simply the sum of all harmony values.

Input Format:

• The first line contains two integers \(n\) and \(m\) — the number of communities and the number of roads.
• The second line contains \(n\) integers \(H_1, H_2, \dots, H_n\) representing the harmony value for each community.
• Then follow \(m\) lines, each containing two integers \(u\) and \(v\) which denote an undirected road between communities \(u\) and \(v\).

Output Format:

• Output a single integer, the maximum lost harmony value in the worst-case scenario.

Sample Input 1:

1 0
5

Sample Output 1:

5

Sample Input 2:

2 1
3 4
1 2

Sample Output 2:

7

Sample Input 3:

4 3
1 2 3 4
1 2
2 3
3 4

Sample Output 3:

10

Note: Since an independent dominating set always exists in any graph with an edge, the adversaries can always cover the entire city. Hence, the answer is the sum of all harmony values.

inputFormat

The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers \(H_1, H_2, \dots, H_n\). Each of the next \(m\) lines contains two integers \(u\) and \(v\), representing an undirected road between communities \(u\) and \(v\).

outputFormat

Output a single integer: the maximum lost harmony value.

sample

1 0
5

5