Marele erou Ben10 se află din nou în postura de a salva lumea. De data aceasta el trebuie să dezamorseze o bombă de mare putere, a cărei explozie ar putea distruge omenirea. Dificultatea sarcinii constă în faptul că bomba este protejată printr-un dispozitiv complicat, cu cifru, compus din NxN butoane aşezate sub forma unui tablou cu N linii şi N coloane, fiecare buton având înscris un număr natural, aşa cum se vede în figura 1.



Dispozitivul conţine mai multe rame mobile (reprezentate în figură prin pătrate concentrice haşurate diferit), care se pot roti cu 90, 180, 270 sau 360 de grade spre stânga sau spre dreapta, modificând astfel modul de dispunere a numerelor înscrise pe butoanele dispozitivului. Pentru exemplul din figura 1, avem un număr de 3 rame, reprezentate în figură prin culori de fond diferite.
Bomba se dezamorsează dacă suma elementelor de pe prima linie (cea din nord) a fiecărei rame este maximă (zona haşurată din figura 2). Convenim să numim această porţiune a tabloului zona de nord.

Cerinţă

Scrieţi un program care să determine suma elementelor din zona de nord a tabloului, atunci când ramele cifrului au fost aduse în poziţia ce dezamorsează bomba, precum şi configuraţia tabloului.

Date de intrare

Fişierul de intrare cifru.in conţine
pe prima linie numărul natural N, reprezentând numărul liniilor şi coloanelor tabloului.
Pe fiecare dintre următoarele N linii se află câte N numere naturale, separate prin câte un spaţiu, reprezentând numerele înscrise pe butoanele dispozitivului.

Date de ieşire

Fişierul de ieşire cifru.out va conţine pe prima linie un număr natural S reprezentând suma maximă posibil de obţinut în zona de nord a tabloului. Pe următoarele N linii se vor afişa elementele tabloului obţinut prin rotaţia ramelor în poziţia ce dezamorsează bomba (câte N elemente separate prin câte un spaţiu).

Restricţii

1 < N < 101
Numerele înscrise pe butoanele cifrului sunt numere naturale între 0 şi 1000.
O ramă este compusă din cel puţin 2 linii şi două coloane.
Se garantează că, pentru fiecare ramă, suma maximă se poate obţine pe o singură latură.

Exemple

cifru.in	cifru.out	Explicaţii
5 5 1 1 1 4 5 0 0 0 2 5 1 0 2 2 5 2 3 4 2 7 3 3 3 8	36 7 5 5 5 5 3 4 3 2 1 3 2 0 1 1 3 0 0 0 1 8 2 2 2 4	Cifrul din exemplu este compus din două rame. Prima ramă, cea exterioară, a fost rotită cu 90 de grade spre stânga, iar a doua ramă a fost rotită cu 180 de grade spre stânga sau spre dreapta. Suma elementelor îngroşate este 36, fiind cea mai mare sumă posibil de obţinut prin rotirea în toate modurile a celor două rame.

autor: Prof. Alin Burţa

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com