Wyobraź sobie zaskoczenie Bessie, gdy zobaczyła leprechauna skaczącego przez północne pastwisko. Nie dając się nabrać, ruszyła i złapała go chwytnymi kopytami.

„Jedno życzenie, krowo. Tyle mam dla krów”, powiedział.

„Bogactwo”, powiedziała marzycielsko Bessie. „Szansa na bogactwo”.

Leprechauny nigdy nie spełniają życzeń swoich łowców najprostszym sposobem. Gdy opadł dym głośnej eksplozji, lśniący pączek z dziurką obracał się powoli nad bujnymi zielonymi polami.

„Zrobiłem ci torus”, powiedział łagodnie. „Jest na nim macierz $N\times N$ $(1 \le N \le 200)$ liczb całkowitych $-1{,}000{,}000,\ldots,1{,}000{,}000$, określająca bogactwo. Wśród wszystkich ciągów na torusie znajdź spójny ciąg liczb w jednym wierszu, kolumnie lub przekątnej o największej sumie”.

Bessie pomyślała i zrozumiała, że torus „zawija” kolumny, wiersze i przekątne, więc można wybierać kolejne elementy przechodzące przez boczną lub górną krawędź.

Bessie poda macierz. Znajdź największą sumę, wybierając co najmniej jeden element.

Dla przykładu lewa macierz $4\times4$ poniżej ma zaznaczone wszystkie elementy jednej zawiniętej przekątnej:

           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

Zaznaczona przekątna prawej macierzy ma dwie dziewiątki (najwyższą wartość) i szóstkę, razem 24. To najlepsza suma i używa tylko trzech z czterech możliwych elementów przekątnej.

Wejście

• Wiersz 1: jedna liczba całkowita $N$.
• Wiersze $2,\ldots,N+1$: wiersz $i+1$ zawiera $N$ liczb całkowitych oddzielonych spacjami, tworzących wiersz $i$ macierzy.

Wyjście

• Wiersz 1: liczba całkowita, największa suma według tych zasad.

Przykład

Wejście 1

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

Wyjście 1

24

Źródło zadania: adaptacja z BOI'98, 2008