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ătoarele M 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
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.