== include(page="template/taskheader" task_id="pastrafaceri") ==

Poveste şi cerinţă...

Tara in care traieste afaceristul Sorin Pastrama contine $N$ orase, unite intre ele prin $M$ drumuri bidirectionale. Aceasta tara este putin cam dubiosa deoarece ea contine numai cicluri de lungime impara. Cu alte cuvinte, tara este un graf cu $N$ noduri si $M$ muchii, conex, care are numai cicluri de lungime impara. Bineinteles, Pastrama are cate o afacere in fiecare oras. Ca orice afaceri, unele sunt profitabile, altele nu. Asa ca vom nota "profitul" afacerii din orasul $i$ cu un numar intreg $val$~$i$~.
 
h2. Cerinta
 
S-ar putea ca pastrarea tuturor afacerilor sa nu-i aduca niciun profit lui Pastrama, asa ca el va roaga sa-l ajutati si sa ii spuneti care e valoarea maxima pe care o poate obtine daca el poate alege sa pastreze o submultime de afaceri care sunt conectate intre ele. Cu alte cuvinte, el doreste sa afle care este suma maxima a valorilor unui subgraf conex.

h2. Date de intrare

Fişierul de intrare $pastrafaceri.in$ ...
n m
val1 val2 ... valn
x1 y1
x2 y2
...
xm ym

Fişierul de intrare $pastrafaceri.in$ contine pe prima linie numerele naturale $N$ si $M$, cu semnificatiile din enunt. Pe urmatoarea linie se afla $N$ numere intregi, a $i$-a fiind valoarea nodului $i$. Pe urmatoarele $M$ linii se afla cate doua numere naturale $x$ si $y$, ce reprezinta ca avem o muchie bidirectionala intre nodurile $x$ si $y$.

h2. Date de ieşire

În fişierul de ieşire $pastrafaceri.out$ ...

În fişierul de ieşire $pastrafaceri.out$ se va afla un numar natural care reprezinta valoarea maxima care poate fi obtinuta.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 3 * 10^5^$
* $1 ≤ M ≤ 4 * 10^5^$
* $-10^6^ ≤ $val$~$i$~ ≤ 10^6^$
* Un ciclu este orice traseu care pleaca dintr-un nod, ajunge in acelasi nod, si trece prin fiecare muchie cel mult o data. Lungimea acestuia este numarul de muchii parcurse (asta inseamna ca se poate trece printr-un nod de mai multe ori dar nu printr-o muchie)
* **Graful dat va contine numai cicluri de lungime impara**
* Se poate sa nu se aleaga niciun nod, valoarea acestei solutii fiind $0$
* **Atentie la numele fisierului de intrare - pastrafaceri.in in loc de pastramasiafacerile.in**
* **Atentie la numele fisierului de iesire - pastrafaceri.out in loc de pastramasiafacerile.out**
* Buzunarul lui Sorin Pastrama vorbeste orice limba isi doreste

h2. Exemplu
table(example). |_. pastrafaceri.in |_. pastrafaceri.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 4
-1 3 -2 4
1 2
2 3
3 1
1 4
| 6

|
h3. Explicaţie

...

Alegem nodurile $1$, $2$ si $4$ care au suma valorilor egala cu $6$.
Se putea obtine o valoarea mai mare selectand doar nodurile $2$ si $4$, dar acestea nu sunt conectate intre ele.

== include(page="template/taskfooter" task_id="pastrafaceri") ==