Identify the time complexity of the following code as constant, linear, quadratic, cubic, log(n), nlog(n) or NP-hard. //Utilities
import java.io.*;
import java.util.*;

public class Main {
	static int n, m, k;
	static int[][] horW, verW;
	static int[][][] dp = new int[505][505][15];
	
	public static void main(String[] args) throws IOException {
		for (int i = 0; i < 505; i++) {
			for (int j = 0; j < 505; j++) {
				for (int k = 0; k < 15; k++) {
					dp[i][j][k] = -1;
				}
			}
		}
		n = in.iscan(); m = in.iscan(); k =in.iscan();
		horW = new int[n+1][m]; verW = new int[n][m+1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m-1; j++) {
				horW[i][j] = in.iscan();
			}
		}
		for (int i = 1; i <= n-1; i++) {
			for (int j = 1; j <= m; j++) {
				verW[i][j] = in.iscan();
			}
		}
		int min = Integer.MAX_VALUE;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (k % 2 == 1) {
					out.print(-1 + " ");
					continue;
				}
				out.print(dfs(i, j, k/2) * 2 + " ");
			}
			out.println();
		}
		out.close();
	} 
	
	static int dfs(int r, int c, int k) {
		if (dp[r][c][k] != -1) {
			return dp[r][c][k];
		}
		if (k == 0) {
			return dp[r][c][k] = 0;
		}
		int min = Integer.MAX_VALUE;
		if (r - 1 >= 1) {
			min = Math.min(min, verW[r-1][c] + dfs(r-1, c, k-1));
		}
		if (r + 1 <= n) {
			min = Math.min(min, verW[r][c] + dfs(r+1, c, k-1));
		}
		if (c - 1 >= 1) {
			min = Math.min(min, horW[r][c-1] + dfs(r, c-1, k-1));
		}
		if (c + 1 <= m) {
			min = Math.min(min, horW[r][c] + dfs(r, c+1, k-1));
		}
		return dp[r][c][k] = min;
	}
	
	static INPUT in = new INPUT(System.in);
	static PrintWriter out = new PrintWriter(System.out);
	private static class INPUT {

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;

		public INPUT (InputStream stream) {
			this.stream = stream;
		}

		public INPUT (String file) throws IOException {
			this.stream = new FileInputStream (file);
		}

		public int cscan () throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read (buf);
			}
			
			if (numChars == -1)
				return... Complexity: