Imaginez la surprise de Bessie voyant un leprechaun gambader dans le pâturage nord. Loin d'être dupe, elle fonce et le capture avec ses sabots préhensiles.

« Un vœu, bovin. C'est tout ce que j'ai pour les vaches », dit-il.

« La richesse », dit rêveusement Bessie. « L'occasion de s'enrichir. »

Les leprechauns ne réalisent jamais les vœux de leurs ravisseurs sous leur forme la plus facile. Après le fracas d'une explosion, la fumée se dissipe et un beignet scintillant tourne lentement au-dessus des champs verdoyants.

« Je t'ai fait un tore », murmure-t-il. « Il porte une matrice $N\times N$ $(1 \le N \le 200)$ d'entiers dans $-1{,}000{,}000,\ldots,1{,}000{,}000$ qui déterminera ta richesse. Parmi toutes les suites du tore, trouve une suite d'entiers contigus dans une même ligne, colonne ou diagonale dont la somme est maximale. »

Bessie réfléchit et comprend que le tore « reboucle » les colonnes, lignes et diagonales : on peut choisir des éléments contigus qui passent par le bord latéral ou supérieur.

Bessie vous donne la matrice. Trouvez la plus grande somme possible, en choisissant au moins un élément.

Par exemple, la matrice $4\times4$ de gauche ci-dessous marque tous les éléments d'une diagonale qui reboucle :

           8  6  6* 1           8  6* 6  1
          -3  4  0  5*         -3  4  0  5
           4* 2  1  9           4  2  1  9*
           1 -9* 9 -2           1 -9  9*-2

La diagonale marquée à droite contient deux 9 (le plus grand nombre disponible) et un 6, somme 24. C'est la meilleure somme, avec seulement trois des quatre éléments de la diagonale.

Entrée

• Ligne 1 : un entier $N$.
• Lignes $2,\ldots,N+1$ : la ligne $i+1$ contient $N$ entiers séparés par des espaces formant la ligne $i$ de la matrice.

Sortie

• Ligne 1 : un entier, la plus grande somme selon ces règles.

Exemples

Entrée 1

4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

Sortie 1

24

Source du problème : adapté de BOI'98, 2008