آقای مهندس مرحله‌ی جدیدی برای بازی جدیدش، Untrusted طراحی کرده‌است. در این مرحله یک جدول $n \times m$ قرار دارد که باید برای هر یک از خانه‌های آن یکی از جهات راست، پایین، چپ یا بالا انتخاب شود. خانه‌ای که در ستون $j$ام سطر $i$ام جدول قرار دارد را با $(i, j)$ نشان می‌دهیم. سطر‌های جدول از بالا به پایین با اعداد $1$ تا $n$ و ستون‌ها‌ی آن از چپ به راست با اعداد $1$ تا $m$ شماره‌گذاری شده‌اند.
با شروع بازی یک ربات در خانه‌ی $(1, 1)$ (خانه‌ی بالا چپ) جدول قرار می‌گیرد و مطابق با جهت خانه‌های جدول حرکت می‌کند. (اگر جهت یک خانه به سمت بیرون از جدول باشد، ربات در جای خود ثابت می‌ماند و حرکت نمی‌کند). شما فقط در صورتی برنده‌ی بازی می‌شوید که ربات با توجه به جهت‌دهی شما به خانه‌ی $(n, m)$ برسد. دقت کنید که لازم نیست ربات در این خانه بماند و فقط کافی است حداقل یک‌بار آن را ببیند.
آقای مهندس از شما خواسته که این مرحله از بازی را برایش تست کنید. هدف شما این است که با کمترین هزینه ممکن برنده‌ی بازی شوید. هزینه‌ی یک جهت‌دهی برابر است با مجموع هزینه‌ی تمام خانه‌های جدول و هزینه‌ی یک خانه با توجه به جهتی که برای آن انتخاب می‌شود، مشخص می‌شود. (دقت کنید که باید برای تمامی خانه‌های جدول یک جهت تعیین شود)
برنامه‌ای بنویسید که با گرفتن هزینه‌ی مربوط به جهت‌های مختلف خانه‌های جدول، کمترین هزینه‌ی ممکن برای برنده‌شدن را پیدا کند.
در تنها سطر خروجی کمترین هزینه برای برنده‌شدن در بازی را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 3 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 | 29 |
| 4 5 1 1 1 1 1 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 1 1 1 1 1000 1000 1000 1000 1 1 1000 1000 1000 1 1 1000 1000 1000 1000 1 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 1 1000 1000 1000 1000 1000 1 1 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 1000 1000 1000 1000 1000 1000 1000 | 2018 |