palindrom

Un număr se numește palindrom dacă citit de la stânga la dreapta este identic cu numărul citit de la dreapta la stânga. De exemplu, numerele $131$ și $15677651$ sunt palindromuri. Un număr care nu este palindrom poate fi transformat în palindrom adăugând la dreapta sa una sau mai multe cifre.

Dat fiind un șir de $n$ numere naturale, scrieţi un program care să rezolve următoarele două cerinţe:

1. să se determine numărul minim total de cifre care trebuie să fie adăugate, astfel încât fiecare valoare din șir să fie palindrom;
2. considerând că putem adăuga cel mult $S$ cifre, să se determine numărul maxim de termeni palindrom aflați pe poziții consecutive în șirul obținut.

Date de intrare

Fișierul de intrare palindrom.in conţine pe prima linie numărul $C$, reprezentând cerința care trebuie să fie rezolvată ($1$ sau $2$). Pe cea de a doua linie se află un număr natural $n$, reprezentând numărul de valori din șir. Pe următoarele $n$ linii se află cele $n$ numere din șir, câte un număr pe o linie. Dacă $C = 2$, pe ultima linie a fișierului de intrare se va afla numărul natural $S$ reprezentând numărul maxim de cifre ce pot fi adăugate.

Date de ieșire

Fișierul de ieșire palindrom.out va conţine o singură linie pe care va fi scris răspunsul la cerinţa $C$ din fișierul de intrare.

Restricții și precizări

• $1 \leq n \leq 50 \ 000; 0 \leq S \leq 500 \ 000$;
• Numerele din șir au cel mult $50$ de cifre;
• Pentru $15$ puncte, $C = 1$ și $n = 1$;
• Pentru $10$ puncte, $C = 2$, $S = 0$, $1 < n \leq 100$ și numerele din șir au cel mult $18$ cifre;
• Pentru $14$ puncte, $C = 1$, $1 < n \leq 1 \ 000$ și numerele din șir au cel mult $18$ cifre;
• Pentru $15$ puncte, $C = 2$, $S > 0, 1 < n \leq 1 \ 000$ și numerele din șir au cel mult $18$ cifre;
• Pentru $16$ puncte, $C = 2$, $1 000 < n \leq 50 \ 000$ și numerele din șir au cel mult $18$ cifre;
• Pentru $13$ puncte, $C = 1$, $1 000 < n \leq 50 \ 000$ și numerele din șir au între $19$ și $50$ de cifre;
• Pentru $17$ puncte, $C = 2$, $1 000 < n \leq 50 \ 000$ și numerele din șir au între $19$ și $50$ de cifre;

Exemplul 1

palindrom.in

1
5
12232
131
12345
0
7717

palindrom.out

7

Explicație

$C = 1, n = 5$.

• Pentru a transforma $12232$ în palindrom trebuie să adăugăm minimum două cifre ($1223221$);
• Pentru $12345$ trebuie să adăugăm minimum $4$ cifre ($123454321$);
• Pentru $7717$ trebuie să adăugăm minimum o cifră ($77177$);
• Numerele $131$ și $0$ sunt deja palindromuri.

În total $2+4+1=7$.

Exemplul 2

palindrom.in

2
7
12232
131
12345
0
7717
1244
215809
4

palindrom.out

3

Explicație

$C = 2, n = 7, S = 4$, deci se pot adăuga maximum $4$ cifre.

Putem adăuga cele $4$ cifre numărului $12345$ și obţinem o secvenţă de lungime $3$ formată numai din palindromuri ($131 \ 123454321 \ 0$).
O altă variantă este de a adăuga o cifră la $7717$ și două cifre la $1244$ și obţinem tot o secvenţă de lungime $3$ formată numai din palindromuri ($0 \ 77177 \ 124421$).
Pentru orice altă variantă, secvenţa de palindromuri obţinută are mai puțini termeni.