360硅谷范的工作区被划为了 n 行 m 列的连续工位，每个工位上可以安排一名员工工作。当第 i 行第 j 列（行和列都从1开始编号）的工位中坐着一个颜值为 C 的员工时，公司会需要付出的成本是 (|C + i + j| ⊕ U) * W（其中⊕是按位异或符号）。U 是这个工位的风水指数，W 是这个工位上接收到360安全路由发出的wifi信号强度。

比较有意思的是，两个相邻的工位（同行相邻列或同列相邻行）上坐着颜值为 C₁ 和 C₂ 的员工时，公司会额外付出 |C₁ + C₂| 的成本。

找到一种方案，决定每个工位上的员工应有的颜值 C (|C| ≤ k)，使得公司最终需要付出的总成本最小。并输出需要付出的最小总成本。

输入格式

第一行输入三个整数 n, m, k (1 ≤ k ≤ 30) 分别表示工区的长、宽、和颜值绝对值的上限。

接下来读入两个 n 行 m 列的整数矩阵。

第一个矩阵表示每个工位的风水指数 U_i,j (1 ≤ U_i,j ≤ 30)。

第二个矩阵表示每个工位收到360安全路由发出的wifi信号强度W_i,j (1 ≤ W_i,j ≤ 30 且 W_i,j 为整数)。

对于简单版本，1 ≤ n ≤ 2，1 ≤ m ≤ 3；

对于中等版本，n = 2, 1 ≤ m ≤ 30；

对于困难版本，1 ≤ n, m ≤ 30。

输出格式

输出一个数，表示公司需要付出的最小成本。