Darius

Darius se antrenează pentru competiția IronChild, un concurs de fitness unde rezistența, ritmul și alternanța exercițiilor sunt esențiale. Antrenorul îi propune o listă cu $N$ exerciții identificate prin numere naturale $X_1, X_2, \dots, X_N$. Fiecare exercițiu are un anumit nivel de intensitate și poate fi de tip forță sau cardio.

Pentru concurs, Darius trebuie să-și selecteze din lista primită ce exerciții dorește, dar cu următoarele condiții: să nu aibă exerciții cu intensități egale și să le poată prezenta alternativ în funcție de tip. El este hotărât să câștige competiția, de aceea dorește să aleagă exercițiile astfel încât suma intensităților să fie cea mai mare posibilă.

Intensitatea exercițiului $X_i$ este stabilită astfel: se construiește în $f$ numărul format prin alipirea, în ordine, a tuturor cifrelor impare din $X_i$ și în $c$ numărul format prin alipirea, în ordine, a tuturor cifrelor pare din $X_i$. Dacă $f>c$ sau $X_i$ nu are cifre pare atunci exercițiul $X_i$ este de tip forță cu intensitatea $f$, iar dacă $f<c$ sau $X_i$ nu are cifre impare atunci este de tip cardio cu intensitatea $c$.

Cerință

Scrieţi un program care să determine și să afișeze:

1. Numărul intensităților distincte pentru exercițiile de tip forță, respectiv cardio din lista inițială.
2. Intensitatea maximă din exercițiile de tip forță și din cele de tip cardio din lista inițială.
3. Suma maximă posibilă a intensităților distincte obținută din exercițiile alternative alese de Darius.

Date de intrare

Fișierul darius.in conţine pe prima linie cerința — $1$, $2$ sau $3$, pe a doua linie numărul $N$, iar pe a treia linie numerele naturale $X_1, X_2, \dots, X_N$ ce identifică exercițiile propuse lui Darius de antrenorul său.

Date de ieșire

Fișierul darius.out va conține:

• pentru cerința 1: două numere naturale separate printr-un singur spațiu reprezentând, în această ordine, numărul de intensități distincte ale exercițiilor de tip forță, respectiv cardio;
• pentru cerința 2: două numere naturale separate printr-un singur spațiu reprezentând, în această ordine, intensitatea maximă a unui exercițiu de tip forță, respectiv cardio;
• pentru cerința 3: suma maximă posibilă obținută din intensitățile exercițiilor alternative alese pentru concurs.

Restricții și precizări

• $1 < N \leq 100 \ 000$, număr natural
• $X_1, X_2, \dots, X_N$ numere naturale nenule cu maxim $4$ cifre, identifică exerciții de ambele tipuri
• Se acordă pentru fiecare cerință 30 de puncte.

Exemplul 1

darius.in

1
8
41 1265 50 11 3236 172 323 5

darius.out

4 2

Explicație

Exerciții de tip forță:

• $50$ (intensitate $5$);
• $11$ (intensitate $11$);
• $3236$ (intensitate $33$);
• $172$ (intensitate $17$);
• $323$ (intensitate $33$);
• $5$ (intensitate $5$);
• $4$ intensități distincte ($5$, $11$, $33$, $17$).

Exerciții de tip cardio:

• $41$ (intensitate $4$);
• $1265$ (intensitate $26$);
• $2$ intensități distincte ($4$, $26$).

Exemplul 2

darius.in

2
8
41 1265 50 11 3236 172 323 5

darius.out

33 26

Explicație

Intensitatea maximă din exercițiile de tip forță este $33$.

Intensitatea maximă din exercițiile de tip cardio este $26$.

Exemplul 3

darius.in

3
8
41 1265 50 11 3236 172 323 5

darius.out

91

Explicație

O posibilitate de alegere a exercițiilor pentru a obține intensitatea maximă $91$ ar putea fi: $11$ (forță), $41$ (cardio), $3236$ (forță), $1265$ (cardio), $172$ (forță) ($11+4+33+26+17=91)$.