lacate

În vistieria cetății se află $N$ lacăte așezate în linie, numerotate de la $1$ la $N$, fiecare având inscripționat un cod numeric în baza $10$. Definim amprenta unui cod ca fiind un număr format din două cifre, $\overline{XY}$, unde $X$ este cea mai mare cifră a codului, iar $Y$ este cifra cea mai mică. De exemplu pentru codul $327003$ amprenta este $70$.

Două lacăte din șir situate pe pozițiile $i$ și $j$ formează o pereche echilibrată dacă $i < j$ și codurile lor $Cod[i]$ și $Cod[j]$ au aceleași cifre, indiferent de ordinea și numărul de apariții al acestora. De exemplu, dacă primul lacăt din șir și al treilea au codurile $Cod[1] = 1221$ și $Cod[3] = 211$, atunci perechea ($Cod[1]$, $Cod[3]$) este echilibrată deoarece ambele sunt formate exact din cifrele $\{1, 2\}$ și $1 < 3$.

Cerințe

Scrieți un program care rezolvă următoarele cerințe, cerința de rezolvat fiind dată de $C \in \{1, 2, 3\}$:

$C=1$. Determinați câte lacăte au amprenta formată din două cifre identice.

$C=2$. Considerăm că din fiecare cod trebuie să eliminăm exact o apariție a unei cifre, astfel încât suma amprentelor rezultate să fie maximă. Determinați această sumă.

$C=3$. Determinați numărul total de perechi echilibrate din șirul inițial al celor $N$ lacăte.

Date de intrare

Fișierul de intrare lacate.in conține pe prima linie numărul $C$ reprezentând cerința care trebuie rezolvată. Pe a doua linie, numărul $N$. Pe a treia linie, în ordine cele $N$ coduri, numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire lacate.out va conține pe prima linie un singur număr reprezentând răspunsul la cerința rezolvată.

Restricții și precizări

• $1 \le N \le 50 \ 000$;
• $1 \le$ Codul oricărui lacăt din șir $\le 100 \ 000$
• Pentru $C = 2$, codul oricărui lacăt din șir $\ge 10$

Exemplul 1

lacate.in

1
8
132 213 34 334 4343 2 1223 666

lacate.out

2

Explicație

Amprentele lacătelor sunt $31 \ 31 \ 43 \ 43 \ 43 \ 22 \ 31 \ 66$ și avem $2$ amprente cu cifre identice $22$ și $66$.

Exemplul 2

lacate.in

2
8
132 213 34 334 4343 20 1223 666

lacate.out

314

Explicație

Codurile obținute după eliminarea câte unei cifre vor fi: $32 \ 23 \ 4 \ 34 \ 443 \ 2 \ 223 \ 66$, generând amprentele: $32 \ 32 \ 44 \ 43 \ 43 \ 22 \ 32 \ 66$, cu suma $314$.

Exemplul 3

lacate.in

3
8
132 213 34 334 4343 2 1223 666

lacate.out

6

Explicație

Perechile echilibrate sunt $(132, 213)$, $(132, 1223)$, $(213, 1223)$, $(34, 334)$, $(34, 4343)$, $(334, 4343)$.