خانه‌های یک جدول $n\times m$، با اعداد صحیح نامنفی پر شده‌اند. می‌خواهیم از مکانی دلخواه در سطر اول این جدول حرکت کرده به یکی از خانه‌های سطر آخر برسیم به گونه‌ای که مجموع اعداد خانه‌هایی که از آن‌ها گذشته‌ایم بیشینه گردد.

اما برای این کار ملزرم به رعایت قوانین زیر هستیم:

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

برنامه‌ای بنویسید که مجموع بیشینه‌ی اعداد مسیر را پیدا کند.

در فایل ورودی ابتدا عدد $n$ و سپس عدد $m$ آمده است. سپس در $n$ سطر بعد، در هر سطر $m$‌عدد به نشانه درایه‌های جدول آمده است. فرض کنید تمام مقادیر ورودی در Integer جا می‌گیرند و در ضمن: $m,n\leq 700$.

در فایل خروجی جواب را چاپ کنید.

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