Dodel manelistul a fost surprins de către domnul profesor de informatică în timp ce asculta manele la căști în timpul orei de informatică. Domnul profesor îi dă să rezolve o problemă de informatică, iar dacă nu reușește până la finalul orei, Dodel va fi pedepsit să asculte muzică rock până la finalul anului școlar. Disperat de această perspectivă sumbră, Dodel vă roagă sa îl ajutați să rezolve problema de informatică primită.

Cerinţa

Se dă o matrice cu n linii şi n coloane şi elemente numere întregi. Calculaţi cel mai mare produs care se poate obține prin înmulțirea unui element de pe diagonala principală cu unul de pe diagonala secundară.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n*n numere întregi, separate prin spaţii, reprezentând elementele matricei, linie cu linie.

Date de ieşire

Programul afișează pe ecran numărul max, reprezentând valoarea calculată.

Restricţii şi precizări

• 1 ≤ n ≤ 20 și este număr par
• elementele matricei vor din intervalul [-100000,100000].
• Nu se știe exact cum a reușit Dodel să intre la specializare matematică-informatică și nici cum a reusit să ia legătura cu voi ca să vă ceară ajutorul.
• Problema dată este destul de ușoară, dar dacă nu doriți să il ajutați pe Dodel, atunci nu rezolvați problema.

Exemplu:

Date de intrare

4
8 3 3 7 
1 1 -6 5 
-8 7 -1 1 
9 8 7 -1 

Date de ieșire

72

Explicație

Dacă se alege elementul 8 de pe diagonala principală și elementul 9 de pe cea secundară, atunci se obține produsul maxim cerut.