Description

LYK 有一个 n * m 的网格图，每个格子都填有-1 至 n * m-1 中的其中一个数表示它的颜色且每个格子都有一个代价ai,j。

它想选择一个四联通块，使得该四联通块中，存在至少 k 种不同的颜色，且不包含-1，

要使得所选的格子的代价和最小。

Format

Input

第一行三个整数，n,m,k.

接下来n行，每行m个数，表示矩阵每个位置的颜色，每个数在-1到 n*m-1之间。

接下来n行，每行m个数，表示选择该位置所需要的代价。

对于100%的数据：1<=n,m<=15，1<=k<=7，1<=ai,j<=100000。

Output

一行，表示最小代价和。

Samples

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

7