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ă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 și precizări

• $ 1 \leq N \leq 100 000$

• $ 1 \leq M \leq 150 000$

• $ 1 \leq x, y \leq N$

• $ 1 \leq p_i \leq 10 000$, pentru orice $i$, $ 1 \leq i \leq 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 \leq 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 = 8$ staț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$.