Stell dir Bessies Überraschung vor, als ein Leprechaun durch die Nordweide hüpfte. Sie lässt sich nicht täuschen, stürmte auf ihn zu und fing ihn mit ihren Greifhufen.

„Ein Wunsch, Kuh. Mehr habe ich für Kühe nicht“, sagte er.

„Reichtum“, sagte Bessie verträumt. „Die Gelegenheit zu Reichtum.“

Leprechauns erfüllen die Wünsche ihrer Fänger nie auf die einfachste Art. Nach einer lauten Explosion verzog sich der Rauch, und ein schimmernder Donut drehte sich langsam über üppigen grünen Feldern.

„Ich habe dir einen Torus gemacht“, sagte er sanft. „Darauf ist eine $N\times N$-Matrix $(1 \le N \le 200)$ mit ganzen Zahlen $-1{,}000{,}000,\ldots,1{,}000{,}000$, die deinen Reichtum bestimmt. Finde unter allen Folgen auf dem Torus eine zusammenhängende Ganzzahlfolge in einer Zeile, Spalte oder Diagonale mit größter Summe.“

Bessie überlegte und erkannte: Der Torus „verbindet“ die Spalten, Zeilen und Diagonalen über den Rand, sodass zusammenhängende Elemente über Seiten- oder oberen Rand gewählt werden können.

Bessie teilt die Matrix mit dir. Bestimme die größte Summe, wobei mindestens ein Element gewählt werden muss.

Als Beispiel zeigt die linke $4\times4$-Matrix unten alle markierten Elemente einer über den Rand laufenden Diagonale:

           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

Die markierte Diagonale rechts enthält zwei Neunen (die größte verfügbare Zahl) und eine Sechs, Summe 24. Das ist die beste Summe und nutzt nur drei der vier möglichen Diagonalenelemente.

Eingabe

• Zeile 1: eine ganze Zahl $N$.
• Zeilen $2,\ldots,N+1$: Zeile $i+1$ enthält $N$ durch Leerzeichen getrennte ganze Zahlen für Matrixzeile $i$.

Ausgabe

• Zeile 1: eine ganze Zahl, die größte Summe nach diesen Regeln.

Beispiele

Eingabe 1

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

Ausgabe 1

24

Aufgabenquelle: adaptiert von BOI'98, 2008