تخيل دهشة 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