דמיינו את הפתעת Bessie כשראתה לפרקון מקפץ במרעה הצפוני. היא אינה טיפשה: הסתערה ותפסה אותו בפרסותיה האוחזות.

״משאלה אחת, פרה. זה כל מה שיש לי לפרות״, אמר.

״עושר״, אמרה Bessie בחלומיות. ״הזדמנות לעושר״.

לפרקונים לעולם אינם מגשימים את משאלות תופסיהם בצורה הקלה ביותר. כשעשן פיצוץ רועש התפזר, סופגנייה טבעתית נוצצת הסתובבה לאט מעל שדות ירוקים שופעים.

״הכנתי לך טורוס״, אמר ברכות. ״עליו מטריצת $N\times N$ $(1 \le N \le 200)$ של שלמים בטווח $-1{,}000{,}000,\ldots,1{,}000{,}000$ שיקבעו את עושרך. מכל הסדרות האפשריות על הטורוס, מצאי סדרת שלמים רציפים בשורה, עמודה או אלכסון אחד עם הסכום הגדול ביותר״.

Bessie חשבה והבינה שהטורוס ״עוטף״ את העמודות, השורות והאלכסונים, כך שאפשר לבחור איברים רציפים שחוזרים דרך הגבול הצדדי או העליון.

Bessie תשתף את המטריצה. מצאו את הסכום הגדול ביותר, תוך בחירת לפחות איבר אחד.

לדוגמה, מטריצת $4\times4$ השמאלית למטה מסמנת את כל איברי אלכסון עוטף אחד:

           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

האלכסון המסומן מימין כולל שתי תשיעיות (המספר הגבוה הזמין) ושש, סכום 24. זה הסכום הטוב ביותר, עם שלושה בלבד מארבעת איברי האלכסון האפשריים.

קלט

• שורה 1: שלם אחד $N$.
• שורות $2,\ldots,N+1$: שורה $i+1$ מכילה $N$ שלמים מופרדים ברווחים היוצרים את שורת המטריצה $i$.

פלט

• שורה 1: שלם, הסכום הגדול ביותר לפי הכללים האלה.

דוגמאות

קלט 1

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

פלט 1

24

מקור הבעיה: עיבוד מ־BOI'98, 2008