metrou

Această problemă este dedicată celor care așteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.

Se dă planul unei rețele de metrou cu N stații și M tuneluri bidirecționale între stații. Două stații de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare stație i are asociat un profit $p_i$ dat.

Henry a fost recent promovat dintr-un post de angajat al departamentului de curățenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii rețele de metrou, Henry trebuie să aleagă o submulțime de stații care vor fi construite, astfel încât oricare două stații alese să nu fie vecine în planul inițial. Pentru a-și păstra poziția în companie, suma profiturilor stațiilor alese în această submulțime trebuie să fie maximă.

Cerință

Dându-se N, M, profiturile aduse de fiecare din cele N stații și planul inițial al rețelei, să se determine suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.

Date de intrare

Pe prima linie a fișierului de intrare metrou.in se vor afla două numere naturale N și M separate printr-un spațiu, reprezentând numărul de stații, respectiv numărul de tuneluri din planul inițial. Pe a doua linie se vor afla N numere naturale separate prin câte un spațiu, al i-lea dintre acestea reprezentând profitul $p_i$ adus dacă stația i ar fi construită. Pe următoareleM linii se vor afla câte două numere naturale x și y separate printr-un spațiu, semnificând faptul că un tunel unește stațiile x și y în planul inițial.

Date de ieșire

În fișierul de ieșire metrou.out se va afișa o singură linie conținând un singur număr natural, reprezentând suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 150 000
• 1 ≤ x, y ≤ N
• $1 ≤ p_i ≤ 10 \ 000$, pentru orice i, 1 ≤ i ≤ N.
• Există maximum 15 stații care se învecinează cu 3 sau mai multe stații în planul dat.
• Există maximum 20 de stații care se învecinează cu exact o stație în planul dat.
• Pentru 20% din teste, N ≤ 20.
• Pentru alte 10% din teste, planul rețelei de metrou este de forma unui lanț simplu într-un graf neorientat.
• Pentru alte 10% din teste, planul rețelei de metrou este de forma unui ciclu simplu într-un graf neorientat.
• Putem ajunge din orice stație în oricare altă stație urmând tunelurile existente în planul inițial.

Exemplu

metrou.in

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

metrou.out

9

Explicaţii

Avem N = 8stații de metrou și M = 10 tuneluri în plan.
Submulțimea de stații {2, 4, 8} asigură profitul maxim de 3 + 5 + 1 = 9.
Observăm că submulțimea respectă regula descrisă în enunț, întrucât nu există niciun tunel care sa unească stațiile 2-4, 2-8 sau 4-8.