+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + سوال الگوریتمی ---------- یک [گراف وزن‌دار](https://fa.wikipedia.org/wiki/%DA%AF%D8%B1%D8%A7%D9%81_%D9%88%D8%B2%D9%86%E2%80%8C%D8%AF%D8%A7%D8%B1) بدون جهت داریم که می‌توانیم آن را به صورت یک شبکه‌ی جدولی هم در نظر بگیریم که دارای $n$ سطر و $m$ ستون است.مجموعه‌ی رئوس گراف را به شکل زیر تعریف می‌کنیم: $$\left\{(i,j)|1\le i \le n,1 \le j \le m\right\}$$ بین دو راس $(i_1,j_1)$ و $(i_2,j_2)$ یال وجود دارد اگر و تنها اگر فاصله‌ی منهتنی آن ها برابر $1$ باشد. (فاصله‌ی منهتنی دو خانه را برابر مجموع فاصله‌های افقی و عمودی خانه‌های جدول تعریف می‌کنیم.) خستگی یک مسیر در گراف برابر مجموع اعدادی است که روی یال‌های آن مسیر نوشته‌شده‌است.(اعداد روی یال‌ها در ورودی آمده است.) شما باید به ازای هر خانه از جدول $n \times m$ (به عبارتی هر راس گراف) پاسخ سوال زیر را مشخص کنید: حداقل میزان خستگی اگر بخواهیم با شروع از این خانه‌ی جدول ، روی یال‌ها حرکت کنیم (حرکت روی یک یال تکراری مجاز است) و بعد از دقیقا $k$ مرحله به خانه‌ی شروع بازگردیم چه قدر است؟ # ورودی خط اول ورودی به ترتیب، شامل سه عدد `n` و `m` و `k`است. `n` خط بعدی در هر خط `m-1` عدد می‌آیند که $j$ امین عدد از $i$ امین خط عدد روی یال بین دو خانه‌ی $(i, j)$ و $ (i, j+1)$ را مشخص می‌کند. `n-1` خط بعدی در هر خط `m` عدد می‌آیند که $j$ امین عدد از $i$ امین خط عدد روی یال بین دو خانه‌ی $(i, j)$ و $(i+1, j) $ را مشخص می‌کند. $$n,m \le 500$$ $$k \le 20$$ # خروجی یک جدول $n\times m$ که در خانه‌ی $i,j$ آن جواب سوال برای خانه‌ی $(i, j)$ باشد و اگر نمی‌توانستیم بعد از دقیقا $k$ حرکت به خانه‌ی اولیه‌ بازگردیم `-1` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` <mark title="n" class="red">4</mark> <mark title="m" class="orange">4</mark> <mark title="k" class="yellow">10</mark> 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ``` ## خروجی نمونه ۱ ``` 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 ``` ## ورودی نمونه ۲ ``` <mark title="n" class="red">4</mark> <mark title="m" class="orange">4</mark> <mark title="k" class="yellow">1</mark> 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ``` ## خروجی نمونه ۲ ``` -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ```