• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر

---

آقای مهندس مرحله‌ی جدیدی برای بازی جدیدش،‌ Untrusted طراحی کرده‌است. در این مرحله یک جدول $n\times m$ قرار دارد که باید برای هر یک از خانه‌های آن یکی از جهات راست، پایین، چپ یا بالا انتخاب شود. خانه‌ای که در ستون $j$-ام سطر $i$-ام جدول قرار دارد را با $(i,j)$ نشان می‌دهیم. سطر‌های جدول از بالا به پایین با اعداد $1$ تا $n$ و ستون‌ها‌ی آن از چپ به راست با اعداد $1$ تا $m$ شماره‌گذاری شده‌اند.

با شروع بازی یک ربات در خانه‌ی $(1,1)$ (خانه‌ی بالا چپ) جدول قرار می‌گیرد و مطابق با جهت خانه‌های جدول حرکت می‌کند. (اگر جهت یک خانه‌ به سمت بیرون از جدول باشد، ربات در جای خود ثابت می‌ماند و حرکت نمی‌کند). شما فقط در صورتی برنده‌ی بازی می‌شوید که ربات با توجه به جهت‌دهی شما به خانه‌ی $(n,m)$ برسد. دقت کنید که لازم نیست ربات در این خانه بماند و فقط کافی است حداقل یک‌بار آن را ببیند.

آقای مهندس از شما خواسته که این مرحله از بازی را برایش تست کنید. هدف شما این است که با کمترین هزینه ممکن برنده‌ی بازی شوید. هزینه‌ی یک جهت‌دهی برابر است با مجموع هزینه‌ی تمام خانه‌های جدول و هزینه‌ی یک خانه با توجه به جهتی که برای آن انتخاب می‌شود، مشخص می‌شود. (دقت کنید که باید برای تمامی خانه‌های جدول یک جهت تعیین شود)

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

ورودی

در سطر اول ورودی به ترتیب دو عدد طبیعی $n$، تعداد سطر‌ها و $m$، تعداد ستون‌ها، آمده است.

در هر یک از$n$ سطر‌ بعدی، $m$‌ عدد طبیعی آمده‌است که $j$-امین عدد سطر $i$-ام، نشان‌دهنده‌ی هزینه‌ی گذاشتن جهت راست در خانه‌ی $(i,j)$‌ است. در ادامه سه جدول دیگر به همین شکل آمده‌است که به ترتیب هزینه گذاشتن جهت‌های پایین، چپ و بالا در خانه‌های جدول را نشان می‌دهد. بین هر دو جدول پشت‌سرهم یک سطر خالی آمده است. تضمین می‌شود تمامی اعداد ورودی بین $1$ تا $1\ 000\ 000$ هستند.

$$2\le n,m \le 500$$

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۲۰	$ n,m \le 50 $
۲	۱۰	$ n = 2 $
۳	۲۰	هزینه جهت‌های بالا و چپ دقیقا $1\ 000\ 000$ است و هزینه جهت‌های راست و پایین حداکثر $1\ 000$ است.
۴	۱۰	تمام هزینه‌ها یا ۱ است یا ۲
۵	۴۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

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

(۲۴امین دوره المپیاد کامپیوتر - آزمون دوم - ۱۳۹۳/۰۵/۳۰)