Given an nxm board with a number between -1 and nxm in every entries.
And an nxm matrix M is also given, where M(i,j) is the cost of selecting the (i,j) entry of the given board.

Your task is to find a connected block (which means these entries can reach each other by just go up, down, left and right without going out the block) in the board that contains at least K distinct positive numbers without any -1, and it must have minimum total cost for selecting these entries. Output the minimum total cost.

INPUT

First line consists of three integers, n, m, K (1 ≤ n, m ≤ 15, 1 ≤ K ≤ 7).
Then follows are two n*m matrices, the first matrix denotes the numbers on the board and the second matrix denotes the cost of every entry.

Namely, the first n lines contain m integers, where the jth number in ith line denotes the number on the entry (i,j) of the board. These integers are in [-1, n*m].

Next n lines contain m integers too. The jth number in ith line denotes the cost of selecting the entry (i,j) of the board. These integers are in [1, 100000].

OUTPUT

Print only one line containing the minimum cost to finish the task. If the task is impossible, output -1 please.

SAMPLE INPUT
3 3 3
0 0 1
2 3 3
-1 2 1
3 1 5
4 10 1
9 3 4

SAMPLE OUTPUT
8

见题面

见题面