O tablă de şah de dimensiune nxn conţine pe toate pătrăţelele câte o piesă cu una dintre culorile: alb, negru, roşu, verde sau albastru. Pe tablă nu există 3 piese consecutive de aceeaşi culoare situate pe aceeaşi linie sau coloană.
O mutare presupune interschimbarea a două piese alăturate, fie pe o linie, fie pe o coloană. După mutare se acordă punctaj dacă se obţin următoarele situaţii şi nu numai:
• 3 piese de aceeaşi culoare consecutive pe o linie sau o coloană = 1 punct;
• 3 piese de aceeaşi culoare consecutive pe o linie şi o coloană = 5 puncte;
La orice situaţie de mai sus, o piesă în plus de aceeaşi culoare mai contribuie cu încă 1 la punctaj. De exemplu, 4 piese de aceeaşi culoare consecutive pe o linie sau o coloană = 2 puncte.
Punctajele obţinute de piesele interschimbate se adună.
Punctajul este 0 dacă nu se obţin măcar 3 piese consecutive de aceeaşi culoare.
Cerinţă
Găsiţi cel mai mare punctaj obţinut în urma unei singure mutări.
Date de intrare
Fişierul de intrare tabla.in conţine, pe prima linie, numărul natural n, ce reprezintă dimensiunea tablei. Pe fiecare dintre următoarele n linii se află câte n valori separate prin spaţii. Valorile posibile pot fi: 1, 2, 3, 4 şi 5. Valoarea 1 reprezintă piesa de culoare albă, 2 piesa de culoare neagră etc.
Date de ieşire
Fişierul de ieşire tabla.out va conţine o singură linie pe care va fi scris cel mai mare punctaj obţinut.
Restricţii
• 3 <= n <= 20
Exemple
tabla.in
tabla.out
Explicaţii
3
1 1 2
2 2 1
3 4 5
2
prin interschimbarea elementului (1,3) cu (2,3) se obţine:
1 1 1
2 2 2
3 4 5
şi am 1 punct din prima linie şi 1 punct din a doua linie