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

---

آقا فیروز به تازگی کارهای مدیریت ساختمان خود را با استفاده از نرم‌افزار سبزپرداز انجام می‌دهد؛ این نرم‌افزار به او کمک می‌کند تا کارهایش را خیلی سریع‌تر انجام دهد و وقت بیشتری برای بازی با نوروز داشته باشد.

به همین منظور او یک جدول $n \times m$ بر روی زمین کشید و در هر کدام از خانه‌های آن، تعدادی کشمش قرار داد. البته در بعضی از خانه‌های جدول چمن قرار داشت و در آن‌ها کشمش نگذاشت (سطرهای جدول از بالا به پایین از ۱ تا $n$ و ستون‌ها از چپ به راست با ۱ تا $m$ شماره‌گذاری شده‌اند).

حال نوبت نوروز است که بازی کند. او ابتدا باید یکی از خانه‌های سطر پایین جدول (سطر شماره $n$) را انتخاب کند و بر روی آن برود. سپس طبق گفته آقا فیروز هر بار می‌تواند یکی از دو حرکت زیر را انجام دهد (به شرطی که به خانه‌ای که چمن دارد و یا خارج از جدول است نرود):

• یک خانه به چپ برود.
• یک حرکت شبیه اسب شطرنج داشته باشد؛ یعنی ابتدا دو سطر به بالا برود و سپس اگر تاکنون زوج بار از این حرکت استفاده کرده بود، یک خانه به سمت چپ و در غیر این صورت یک خانه به سمت راست برود. (توجه کنید که صرفا باید خانه آخر چمن نداشته باشد و اگر خانه دو سطر بالاتر چمن داشته باشد، مشکلی در حرکت به وجود نمی‌آورد)

هم‌چنین نوروز زمانی می‌تواند به بازی خاتمه دهد که در سطر شماره یک باشد.

از آن‌جایی که نوروز خیلی کشمش دوست دارد، هر زمان که وارد یک خانه می‌شود، همه کشمش‌های آن را برای خودش برمی‌دارد. حال او از شما می‌خواهد تا بگویید با شرایط بالا حداکثر چند کشمش می‌تواند به دست آورد. هم‌چنین اگر مسیری با شرایط بالا وجود نداشته باشد، نوروز نمی‌تواند هیچ کشمشی به دست بیاورد و باید صفر چاپ کنید.

ورودی

در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب طول و عرض جدول بازی را نشان می‌دهند. تضمین می‌شود که $n$ عددی فرد است.

در $i$امین خط از $n$ خط بعدی $m$ عدد آمده است که $j$امین آن‌ها نشان‌دهنده تعداد کشمش‌های خانه واقع در تقاطع سطر $i$ام و ستون $j$ام می‌باشد. این تعداد را با $a_{i, j}$ نشان می‌دهیم. $$ 1 \le n, m \le 1\ 000$$ $$ 0 \le a_{i, j} \le 100\ 000$$ اگر تعداد کشمش‌های واقع در یک خانه صفر باشد، یعنی آن خانه دارای چمن است و نوروز نمی‌تواند بر روی آن برود.

خروجی

در تنها خط خروجی، حداکثر تعداد کشمش‌هایی که نوروز می‌تواند بخورد را چاپ کنید.

مثال

ورودی نمونه ۱

1 5
0 4 2 0 5

خروجی نمونه ۱

6

نوروز می‌تواند از خانه سوم تنها سطر بازی شروع کرده و سپس یک خانه به چپ بیاید و در همان‌جا کار خود را تمام کند که در این صورت ۶ کشمش نصیب او می‌شود.

ورودی نمونه ۲

3 4
7 0 6 10
1 8 3 6
7 0 6 10

خروجی نمونه ۲

16

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