P6815 [PA 2009] Cakes

Pastry chefs from all over the country have come to the cake convention. At the convention, there is a contest where cakes are baked by teams of $3$ pastry chefs. Each team (three pastry chefs) can bake at most one cake, and a pastry chef may belong to multiple teams. Unfortunately, some pastry chefs do not accept each other and will not cooperate with each other. We know how much flour each pastry chef needs to bake a cake. For a team of three, the flour required is the maximum flour requirement among its members. The contest must ensure that every possible team of three pastry chefs that can cooperate is able to bake one cake. Your task is to compute the total amount of flour used during the contest.

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 2.5\times 10^5$), denoting the number of pastry chefs and the number of pairs of pastry chefs who accept each other. The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^6$), where $p_i$ is the flour requirement of the $i$-th pastry chef. The next $m$ lines each contain two distinct integers $a_i, b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), meaning that pastry chef $a_i$ and pastry chef $b_i$ accept each other. No accepting pair appears more than once.

Print one integer on one line, the total amount of flour used during the entire contest.

#### Sample Explanation The following teams exist: $(1,2,3)$, $(1,2,5)$, $(1,3,4)$. They require $5$, $5$, and $4$ units of flour respectively, so the total is $5+5+4=14$. Translated by ChatGPT 5