Immagina la sorpresa di Bessie vedendo un leprecauno saltellare nel pascolo nord. Non essendo sciocca, lo carica e lo cattura con gli zoccoli prensili.

«Un desiderio, bovina. È tutto ciò che ho per le mucche», dice.

«Ricchezze», dice Bessie sognante. «L'opportunità di ricchezza».

I leprecauni non esaudiscono mai i desideri dei catturatori nel modo più semplice. Dissipato il fumo di una forte esplosione, una ciambella scintillante ruota lentamente sui verdi campi rigogliosi.

«Ti ho fatto un toro», dice dolcemente. «Sopra c'è una matrice $N\times N$ $(1 \le N \le 200)$ di interi in $-1{,}000{,}000,\ldots,1{,}000{,}000$ che determina la tua ricchezza. Fra tutte le sequenze sul toro, trova una sequenza di interi contigui nella stessa riga, colonna o diagonale con somma massima».

Bessie riflette e capisce che il toro «riavvolge» colonne, righe e diagonali, permettendo elementi contigui che attraversano il bordo laterale o superiore.

Bessie darà la matrice. Trova la somma massima, scegliendo almeno un elemento.

Per esempio, la matrice $4\times4$ sinistra sotto mostra tutti gli elementi segnati di una diagonale che attraversa il bordo:

           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 segnata a destra contiene due nove (il numero più alto disponibile) e un sei, totale 24. È la somma migliore, usando solo tre dei quattro elementi possibili della diagonale.

Input

• Riga 1: un intero $N$.
• Righe $2,\ldots,N+1$: la riga $i+1$ contiene $N$ interi separati da spazi che compongono la riga $i$.

Output

• Riga 1: un intero, la somma massima secondo queste regole.

Esempi

Input 1

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

Output 1

24

Fonte del problema: adattato da BOI'98, 2008