CF1517D.Explorer Space

You are wandering in the explorer space of the 2050 Conference.

The explorer space can be viewed as an undirected weighted grid graph with size $n\times m$. The set of vertices is ${(i, j)|1\le i\le n, 1\le j\le m}$. Two vertices $(i_1,j_1)$ and $(i_2, j_2)$ are connected by an edge if and only if $|i_1-i_2|+|j_1-j_2|=1$.

At each step, you can walk to any vertex connected by an edge with your current vertex. On each edge, there are some number of exhibits. Since you already know all the exhibits, whenever you go through an edge containing $x$ exhibits, your boredness increases by $x$.

For each starting vertex $(i, j)$, please answer the following question: What is the minimum possible boredness if you walk from $(i, j)$ and go back to it after exactly $k$ steps?

You can use any edge for multiple times but the boredness on those edges are also counted for multiple times. At each step, you cannot stay on your current vertex. You also cannot change direction while going through an edge. Before going back to your starting vertex $(i, j)$ after $k$ steps, you can visit $(i, j)$ (or not) freely.

你正在 2050 大会的探索空间中漫游。

该探索空间可视为一个大小为 $n\times m$ 的无向带权网格图。其顶点集为 ${(i, j)\mid 1\le i\le n,\ 1\le j\le m}$。当且仅当 $|i_1-i_2|+|j_1-j_2|=1$ 时，两个顶点 $(i_1,j_1)$ 与 $(i_2, j_2)$ 之间存在一条边。

每一步，你均可移动至与当前顶点通过一条边相连的任意顶点。每条边上陈列着若干展品。由于你已熟知所有展品，因此每当经过一条包含 $x$ 件展品的边时，你的无聊值便会增加 $x$。

对每个起始顶点 $(i, j)$，请回答如下问题：从 $(i, j)$ 出发，恰好经过 $k$ 步后返回 $(i, j)$，所能达到的最小无聊值是多少？

同一条边可被多次使用，但每次经过该边时，其对应的无聊值均需重复计入。每一步中，你不能停留在当前顶点；在穿过一条边的过程中，也不能改变方向。在第 $k$ 步结束并返回起始顶点 $(i, j)$ 之前，你可以自由地（或不）再次访问 $(i, j)$。

The first line contains three integers $n$, $m$ and $k$ ($2\leq n, m\leq 500, 1\leq k\leq 20$).

The $j$-th number ($1\le j \le m - 1$) in the $i$-th line of the following $n$ lines is the number of exibits on the edge between vertex $(i, j)$ and vertex $(i, j+1)$.

The $j$-th number ($1\le j\le m$) in the $i$-th line of the following $n-1$ lines is the number of exibits on the edge between vertex $(i, j)$ and vertex $(i+1, j)$.

The number of exhibits on each edge is an integer between $1$ and $10^6$.

第一行包含三个整数 $n$、$m$ 和 $k$（$2\leq n, m\leq 500$，$1\leq k\leq 20$）。

接下来 $n$ 行中，第 $i$ 行的第 $j$ 个数（$1\le j \le m - 1$）表示顶点 $(i, j)$ 与顶点 $(i, j+1)$ 之间边上的展品数量。

再接下来 $n-1$ 行中，第 $i$ 行的第 $j$ 个数（$1\le j\le m$）表示顶点 $(i, j)$ 与顶点 $(i+1, j)$ 之间边上的展品数量。

每条边上的展品数量均为介于 $1$ 到 $10^6$ 之间的整数。

Output $n$ lines with $m$ numbers each. The $j$-th number in the $i$-th line, $answer_{ij}$, should be the minimum possible boredness if you walk from $(i, j)$ and go back to it after exactly $k$ steps.

If you cannot go back to vertex $(i, j)$ after exactly $k$ steps, $answer_{ij}$ should be $-1$.

输出 $n$ 行，每行 $m$ 个数。第 $i$ 行第 $j$ 个数 $answer_{ij}$ 应为：从顶点 $(i, j)$ 出发，恰好经过 $k$ 步后返回 $(i, j)$ 所能得到的最小可能的“无聊度”。

若无法恰好经过 $k$ 步后回到顶点 $(i, j)$，则 $answer_{ij}$ 应为 $-1$。

In the first example, the answer is always $10$ no matter how you walk.

In the second example, $answer_{21} = 10$, the path is $(2,1) \to (1,1) \to (1,2) \to (2,2) \to (2,1)$, the boredness is $4 + 1 + 2 + 3 = 10$.

在第一个例子中，无论你如何行走，答案始终为 $10$。

在第二个例子中，$answer_{21} = 10$，路径为 $(2,1) \to (1,1) \to (1,2) \to (2,2) \to (2,1)$，无聊值为 $4 + 1 + 2 + 3 = 10$。