+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز به تازگی کارهای مدیریت ساختمان خود را با استفاده از [نرم‌افزار سبزپرداز](https://sabzpardaz.org/) انجام می‌دهد؛ این نرم‌افزار به او کمک می‌کند تا کارهایش را خیلی سریع‌تر انجام دهد و وقت بیشتری برای بازی با نوروز داشته باشد. به همین منظور او یک جدول $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 ``` در این‌جا نوروز می‌تواند از خانه چهارم سطر سوم شروع کند و سپس با یک حرکت به خانه سوم سطر اول بیاید و دیگر هم نمی‌تواند حرکتی بکند. در این صورت او ۱۶ کشمش به‌دست می‌آورد که با کمی بررسی معلوم می‌شود این مقدار ماکسیمم است. <details class="blue"> <summary> راهنمایی ۱ </summary> فرض کنید می‌خواهیم به ازای هر خانه از جدول می‌خواهیم به دست آوریم که اگر از این خانه شروع کنیم چند کشمش می‌توانیم به دست آوریم و این مقدار را $dp_{i,j}$ بنامید. حال یک رابطه برای به دست آوردن مقدار $dp$ از روی بقیه مقادیر به دست آورید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> اولا که سطرهایی که شماره زوج دارند، اصلا مهم نیستند چون با توجه به حرکات تعریف شده نمی‌توان به آن‌ها رسید. هم‌چنین به ازای بقیه خانه‌ها، اگر شماره سطر آن‌ها را $x$ بنامیم، درصورتی که $(n - x) / 2$ زوج باشد، حرکت اسبی حتما به سمت چپ و در غیر این صورت به سمت راست است. (یعنی زوجیت تعداد حرکت‌های اسبی تا کنون از روی شماره سطر به دست می‌آید) حال با توجه به این موضوع سعی کنید رابطه‌ای برای محاسبه $dp$ گفته شده در بالا پیدا کنید. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> برای محاسبه $dp$ حرکت‌هایی که نوروز می‌تواند انجام دهد را در نظر می‌گیریم؛ نوروز یک خانه به سمت چپ می‌رود یا همان طور که در بالا گفته شد، حرکت اسبی انجام می‌دهد. حال در صورتی که در خانه $(i, j)$ چمن باشد، مقدار $dp$ آن را منفی بی‌نهایت می‌گذاریم و در غیر این صورت مقدار $dp$ را برابر با بیشینه $dp$ دو خانه‌ای که می‌تواند به آن‌ها برسد (البته توجه کنید که ممکن است یکی از این دو خانه، وجود نداشته باشد و نباید به مقدار آن نگاه کنیم). در آخر هم به مقدار $dp$ تعداد شکلات‌های این خانه را اضافه می‌کنیم. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> در نهایت برای محاسبه کردن جواب، بیشینه مقدار $dp$ را در بین سطر آخر پیدا کنید. اگر آن مقدار آن منفی بود، یعنی هیچ مسیری نداریم و جواب صفر است. در غیر این صورت هم جواب برابر با همین مقدار بیشنیه است. </details>

حل سؤال در بانک سؤالات