فهرست مندرجات
Steps
معین پس از انصراف از دوره‌ی تیم المپیاد کامپیوتر تصمیم گرفت در رشته‌ی باستان‌شناسی ادامه تحصیل دهد. به تازگی یکی از اساتید وی به او این مسولیت را داده است که ماکتی از یک پله‌ی قدیمی بسازد. او برای این منظور یک تخته‌ی چوبی $n \times m$ را برش می دهد تا به شکل یک پله ی قدیمی برسد. در زیر نمونه هایی از پله کامل آمده است. دقت کنید که این‌ها تنها نمونه‌هایی از یک پله کامل‌اند و پله کامل می‌تواند به هر اندازه‌ای بزرگ باشد.
یک پله‌ی قدیمی شکلی است که یا یک پله کامل باشد یا اگر یک پله کامل کوچک‌‌تر را سمت راست آن یا بالای آن قرار دهیم، به یک پله‌ی کامل تبدیل شود. به عنوان مثال در شکل‌های زیر قسمت‌های سفید یک پله قدیی را نشان می دهند.
اما قسمت‌های سفید شکل‌های زیر پله قدیمی نیستند.
تنها مشکل معین این است که هر خانه از این تخته‌ی $n \times m$ یک عدد زیبایی دارد و زیبایی یک پله قدیمی برابر است با مجموع زیبایی‌های خانه‌های تشکیل دهنده‌ی آن.
معین از شما می‌خواهد با دانستن زیبایی هر خانه از تخته، زیبایی زیبا ترین پله‌ی قدیمی که با تخته‌ی مورد نظر می‌توان ساخت را به دست آورید. توجه داشته باشید که پله‌ای که معین می‌سازد این خاصیت را دارد که اگر قسمت‌های حذف شده از پله را به آن اضافه کنیم، پله‌ی کامل آن در تخته جا می‌شود.
ورودی
- در ورودی ابتدا دو عدد $n$ و $m$ آمده اند که نشان‌دهنده ی ابعاد تخته می‌باشند.
- سپس در $n$ سطر بعدی در هر سطر $m$ عدد آمده که هر کدام نشان‌دهنده‌ی عدد زیبایی خانه‌ی متناظر با آن در تخته است.
- $1 \leq n,m \leq 500$
- زیبایی خانه‌های تخته بین $-1000$ و $1000$ هستند
- در حداقل ۴۰ درصد تست ها مقدار $n$ و $m$ کمتر یا مساوی ۱۰۰ هستند
خروجی
در تنها سطر خروجی میزان زیایی زیباترین پله قدیمی درون تخته را چاپ کنید.
محدودیت‌ها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 4 3 -2 -3 -4 3 -2 -3 6 1 2 -1 4 | 8 |
توضیحات
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
