Problem Description

Little pig iPig arrives in a city called pigsty, a city specifically prepared for pigs. The city has n residential areas connected by many undirected edges. As a harmonious city, iPig plans to spend the rest of his life here.

Years later, iPig becomes the director of city planning, which makes him very happy. However, at the same time, many anti-harmony activists have grown tired of the harmonious life and are causing trouble throughout the city. To better control the situation, iPig completely reconstructs the city: he destroys all the roads and rebuilds m undirected edges, ensuring that each residential area is part of at most one undirected cycle.

iPig thought this would deter the anti-harmony activists, but after the new roads were built, they declared they would brainwash the residential areas!

This is troublesome. iPig quickly gathers a lot of information. He labels each residential area with a harmony value HX_i, representing the harmony level of the i-th area.

Through underground information, iPig learns that the anti-harmony activists have a pattern: they will target several areas, sending one pig to each, to zero out the harmony values. During this process, each targeted area will also have one pig guarding each of its directly connected areas to prevent interference from police pigs. This plan seems perfect but has a flaw: since the activists know each other only online and have never met in person, to avoid unnecessary trouble (like mistaking pigs), each area can have at most one pig.

iPig suddenly feels immense pressure and wants to know the maximum possible loss of harmony values in the worst-case scenario. However, being unfamiliar with computers, he doesn't know how to calculate this. Can you help him?

Input Format

The first line of input contains two integers n and m, indicating that there are n residential areas in pigsty city and m undirected edges connecting these areas after iPig's reconstruction.

The next line contains n positive integers, where the i-th integer HX_i represents the harmony value of the i-th area.

The following m lines each contain two positive integers a and b (1 <= a, b <= n), indicating an undirected edge connecting area a and area b.

Output Format

Output a single integer on one line, representing the maximum possible loss of harmony values in the worst-case scenario.

Sample Input and Output

Input Sample #1

9 9
2 2 3 4 1 2 3 10 11
1 2
2 3
1 3
3 5
5 4
5 6
4 7
6 7
8 9

Output Sample #1

17

Input Sample #2

5 5
4 4 9 7 7
1 2
2 3
1 4
3 5
5 4

Output Sample #2

9

Notes

Sample Explanation

The anti-harmony activists choose areas 3 (guarding areas 1, 2, and 5), 7 (guarding areas 4 and 6), and 9 (guarding area 8), resulting in a total loss of harmony values of 3 + 3 + 11 = 17.

Alternatively, they could choose areas 1 (guarding areas 2 and 3), 4 (guarding areas 5 and 7), and 9 (guarding area 8), resulting in a total loss of harmony values of 2 + 4 + 11 = 17.

Choosing areas 3, 4, and 9 simultaneously would result in a total loss of 18, but both areas 3 and 4 would need to send pigs to guard area 5, which violates the condition, making this plan infeasible.

Data Constraints

For 20% of the data, each point is not part of any cycle.

For another 30% of the data, the graph contains only one cycle.

For 100% of the data, N <= 1,000,000, M <= 2,000,000, and all harmony values are no more than 1,000.

见题面 Input 部分

见题面 Output 部分