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

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

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

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

• در سطر اول ورودی به ترتیب دو عدد طبیعی $n$، تعداد سطر‌ها و $m$، تعداد ستون‌ها، آمده است.
• در هر یک از $n$ سطر‌ بعدی، $m‌$ عدد طبیعی آمده‌است که $j$امین عدد سطر $i$ام، نشان‌دهنده‌ی هزینه‌ی گذاشتن جهت راست در خانه‌ی $(i, j)‌$ است. در ادامه سه جدول دیگر به همین شکل آمده‌است که به ترتیب هزینه گذاشتن جهت‌های پایین، چپ و بالا در خانه‌های جدول را نشان می‌دهد. بین هر دو جدول پشت‌سرهم یک سطر خالی آمده است.
• $2 \leq n, m \leq 500$
• تمامی اعداد ورودی بین $1$ تا $10^6$ هستند.

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

• زیرمسئله اول (۲۰ نمره): $n, m \leq 50$
• زیرمسئله دوم (۱۰ نمره): $n = 2$
• زیرمسئله سوم (۲۰ نمره): هزینه جهت‌های بالا و چپ دقیقا $10^6$ است و هزینه‌ جهت‌های راست و پایین، دقیقا $1000$ است.
• زیرمسئله چهارم (۱۰ نمره): تمام هزینه‌ها یا $1$ است یا $2$.
• زیرمسئله پنجم (۴۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد