cifre

Elevii clasei pregătitoare se joacă la matematică cu numere. Învățătoarea are un săculeț plin cu jetoane, pe fiecare dintre ele fiind scrisă câte o cifră. Fiecare elev și-a ales din săculeț mai multe jetoane, cu care și-a format un număr. Pentru ca totul să fie mai interesant, elevii s-au grupat în perechi. Doamna învățătoare a oferit fiecărei perechi de elevi câte o cutiuță pentru ca cei doi să își pună împreună jetoanele. De exemplu, dacă unul din elevii unei echipe și-a ales jetoane cu care a format numărul 5137131 iar celălalt elev și-a ales jetoane cu care a format numărul $6551813$, atunci cutiuța echipei va conține $5$ jetoane cu cifra $1$, câte $3$ jetoane cu cifra $3$ și $5$ și câte un jeton cu cifrele $6, 7$ și $8$.

Doar Andrei stătea supărat pentru că numărul de elevi al clasei era impar iar el nu avea partener, motiv pentru care nu și-a mai ales jetoane. Din această cauză, doamna învățătoare i-a spus: “-Alege o echipă din a cărei cutiuță poți lua o parte din jetoane, dar ai grijă ca fiecare dintre cei doi elevi să-și mai poată forma numărul lui din jetoanele rămase, iar tu să poți forma un număr nenul cu jetoanele extrase!“. Dar cum Andrei nu se mulțumea cu puțin, a vrut să aleagă acea echipă din a cărei cutiuță își poată forma un număr de valoare maximă folosind jetoanele extrase.

Cerință

Scrieți un program care să citească numărul $N$ de cutiuțe și numerele formate de elevii fiecărei perechi și care să determine:

1. Numărul de cutiuțe din care Andrei poate lua jetoane respectând condiția pusă de doamna învățătoare;
2. Care este cel mai mare număr nenul pe care îl poate forma Andrei respectând aceeași condiție.

Date de intrare

Fișierul cifre.in conține pe prima linie numărul natural $P$ reprezentând cerința din problemă care trebuie rezolvată. Pe a doua linie numărul natural $N$, iar pe următoarele $N$ linii câte două numere naturale separate printr-un spațiu reprezentând numerele formate de elevii fiecărei perechi.

Date de ieșire

Dacă valoarea lui $P$ este $1$, fișierul de ieșire cifre.out va conține pe prima linie un număr natural reprezentând rezolvarea primei cerințe, adică numărul de cutiuțe din care Andrei poate lua jetoane.

Dacă valoarea lui $P$ este $2$, fișierul de ieșire cifre.out va conține pe prima linie un număr natural reprezentând rezolvarea celei de a doua cerințe, adică numărul maxim pe care îl poate forma Andrei.

Restricții și precizări

• $0 < N \leq 10 \ 000$
• $1 \leq$ numărul de jetoane al fiecarui elev $\leq 9$;
• $0 \leq$ cifra scrisă pe orice jeton $\leq 9$;
• Se garantează că există cel puțin o cutiuță din care Andrei își poate forma număr nenul
• Pentru rezolvarea corectă a fiecărei cerințe se obțin câte $50$ de puncte

Exemplul 1

cifre.in

1
3
1010 2000
12 34
1515 552

cifre.out

1

Explicație

Cu jetoanele extrase din prima cutiuță Andrei nu poate forma un număr diferit de $0$. Din a doua cutiuță Andrei nu poate lua jetoane astfel încât cei doi elevi să își mai poată forma numerele $12$ și $34$. Andrei poate extrage jetoane doar din a treia cutiuță (două jetoane cu cifra $5$).

Exemplul 2

cifre.in

2
5
16815 38861
12 385
5137131 6551813
15033 11583
4704 240

cifre.out

5311

Explicație

Numărul maxim pe care Andrei îl poate forma este $5311$ și se obține din cutiuța a treia.