P2478 [SDOI2010] Urban Planning

Little pig iPig arrived in a city called pigsty. Pigsty is a city specially built for little pigs. There are a total of n communities for pigs to live in, and there are many undirected edges connecting these communities. Because this is a harmonious city, iPig plans to spend the rest of his life here. Years later, iPig became the head of the planning bureau, which made him very happy. However, at the same time, many anti-harmony activists appeared in pigsty. They are tired of such a harmonious life and are making trouble all over the city. To better control the situation, iPig transformed the city: after destroying all the roads, he rebuilt m undirected edges and ensured that each community belongs to at most one cycle formed by undirected edges. iPig thought this would deter the anti-harmony activists. Unexpectedly, after the new city roads were completed, the activists declared they would “brainwash” the city’s communities! This is troublesome. iPig hurriedly collected lots of intelligence. He assigned each community a harmony value HX_i, which represents the harmony level of the i-th community. Through underground sources, iPig learned a pattern in the activists’ attacks: they will choose several communities to act on, sending one pig to each of these communities to set their harmony values to zero. During this process, each chosen community’s directly connected neighboring communities each send a pig to guard it—to prevent interference by police pigs. This plan seems perfect but still has a flaw: since everyone only knows each other online and has not met in person, to avoid unnecessary trouble (like mistaking one pig for another), at most one pig will be present in any community. iPig suddenly feels great pressure. He wants to know how much harmony value could be lost in the worst case. But not knowing computer science, he does not know how to compute it. Can you help him?

The first line contains two integers n and m, indicating that the city pigsty has n communities, and after iPig’s reconstruction, there are m undirected edges connecting the n communities. The next line contains n positive integers. The i-th integer HX_i indicates that the harmony value of the i-th community is HX_i. Then follow m lines. Each line contains two positive integers a and b ($1 \le a, b \le n$), indicating there is an undirected edge between community a and community b.

Output a single integer on one line, indicating the amount of harmony value lost in the worst case.

[Sample Explanation] - The activists choose communities 3 (guarded by communities 1, 2, and 5), 7 (guarded by communities 4 and 6), and 9 (guarded by community 8). The lost harmony value is $3 + 3 + 11 = 17$. - Or they choose communities 1 (guarded by communities 2 and 3), 4 (guarded by communities 5 and 7), and 9 (guarded by community 8). The lost harmony value is $2 + 4 + 11 = 17$. - If they choose communities 3, 4, and 9 at the same time, although the lost harmony value would be $18$, both communities 3 and 4 would need to send pigs to guard community 5, which violates the condition that at most one pig can be present in any community. Therefore, this plan is invalid. [Constraints] - For 20% of the testdata, each node does not belong to any cycle. - For another 30% of the testdata, there is exactly one cycle in the graph. - For 100% of the testdata, $N \le 1000000$, $M \le 2000000$, and all weights are at most $1000$. Translated by ChatGPT 5