یک کرم حلزونی شکل بسیار دراز قصد دارد روی یک ماتریس از اعداد، حمام بگیرد! می‌دانیم کرم برای دراز کشیدن روی ماتریس٬ ابتدا از مسافتی دور به سمت یکی از خانه‌های مجاور چهار ضلع ماتریس حرکت می‌کند تا بتواند در هر حرکت بعد وارد ماتریس شود؛ پس از آن در هر مرحله٬ در صورت امکان یکی از اعمال زیر را انجام می‌دهد:

• یا یک واحد در امتداد جهت حرکت قبلی خود به جلو می‌رود؛ به عنوان مثال٬ اگر در حرکت قبل به سمت راست رفته٬ در این حرکت هم به سمت راست می‌رود.
• یا در امتداد جهت حرکت قبل خود٬ ابتدا $90$ درجه به سمت راست می‌چرخد و سپس یک واحد جلو می‌رود؛ به عنوان مثال٬ اگر در حرکت قبل به سمت راست رفته٬ در این حرکت به سمت پایین می‌رود.
• یا متوقف می‌شود.

می‌دانیم کرم هیچ‌گاه از روی خودش عبور نخواهد کرد و از ماتریس نیز خارج نخواهد شد. بدیهی است که در پایان کار٬ مسیر حرکت کرم یک مارپیچ حلقوی در جهت حرکت عقربه‌های ساعت خواهد بود.

اکنون با فرض این که طول کرم بسیار زیاد است و هیچ وقت دمش وارد ماتریس نمی‌شود٬ به کرم کمک کنید تا طوری حرکت کند که مجموع اعدادی که روی آن‌ها قرار گرفته است٬ بیشینه شود.

• در سطر اول ورودی٬ دو عدد $n$ و $m$ که به ترتیب تعداد سطرها و ستون‌های ماتریس است نوشته شده است.
• سپس در $n$ سطر بعدی ورودی٬ اعداد سطرهای ماتریس به ترتیب آمده است.
• ‎$1 \leq m,n \leq 50$
• $\leq 2 \times 10^5$اعداد ماتریس‎$-2 \times 10^5 \leq$

در تنها سطر خروجی٬ بیش‌ترین مجموع خانه‌های طی شده توسط کرم را بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل