Fillet-O-Fish 1

Peștele de la cap se-mpute!

Cerință

Piedone vă dă un șir $v$ de $N$ numere întregi și $M$ perechi $(a, b)$ de întregi. Știind că se pot șterge oricâte numere din $v$, să se afle suma maximă, respectiv minimă care se poate obține în șirul final dacă pentru fiecare pereche $(a, b)$ dintre cele $M$ date, elementele cu indicii $a$ și $b$ în $v$ pot sta unul lângă celălalt în șirul final. Dacă perechea $(a, b)$ nu este dată, atunci elementele cu indicii $a$ și $b$ în $v$ nu pot sta unul lângă celălalt în șirul final.

Date de intrare

Pe prima linie se vor găsi trei numere întregi: $N$ și $M$. Pe următoarea linie se vor afla $N$ numere întregi, reprezentând șirul $v$. Pe fiecare dintre următoarele $M$ linii, se vor găsi câte două numere întregi, $a$ și $b$.

Dacă folosiți citire cu std::cin, vă recomandăm să adăugați aceste linii la începutul programului:

std::ios_base::sync_with_stdio(0);
std::cin.tie(0);

Date de ieșire

Pe prima linie se vor găsi două numere, reprezentând cele două răspunsuri (primul este maximul, apoi este minimul).

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $-10^9 \leq v_i \leq 10^9$, pentru $i$ de la $1$ la $N$.
• $1 \leq M \leq min(\frac{N \cdot (N-1)}{2}, 200 \ 000)$
• $1 \leq a,b \leq N, a \not= b$
• Perechile $(a, b)$ sunt distincte.
• Pentru fiecare dintre cele două răspunsuri, dacă este corect, veți primi câte $50\%$ din punctaj.

Exemplu

stdin

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

stdout

13 -8

Explicație

Pentru a obține suma maximă, alegem numerele: $8$, $5$ (pe pozițiile $1$, $3$). Am șters numerele de pe pozițiile $2$, $4$, $5$, $6$, $7$.

Pentru a obține suma minimă, alegem numerele: $-2$, $-6$ (pe pozițiile $5$, $7$). Am șters numerele de pe pozițiile $1$, $2$, $3$, $4$, $6$.