#447. 种树

传统 1000 ms 256 MiB
标准 IO
文本比较 admin 标签

题目描述

LCL. 喜欢种树,他在一片 n×mn\times m 的矩形区域内的每一个小方格都种了一棵树,其中在 (i,j)(i,j) 位置的树的类型为 ci,j(1ci,jk)c_{i,j}(1\le c_{i,j}\le k)

7 老师看到了,却说:“你这样是不行的。对于任意位置的树,都需要与和它在同一行或同一列的树相互协调。给定不同种类的树之间的协调系数矩阵 Mk,kM_{k,k},对于在 (i,j)(i,j) 位置的树,定义其协调程度p=1nM[ci,j][cp,j]+q=1mM[ci,j][ci,q]\sum_{p=1}^nM[c_{i,j}][c_{p,j}]+\sum_{q=1}^mM[c_{i,j}][c_{i,q}]。这片区域的美观程度,就等于所有树的协调程度之和。”

LCL. 想知道这片区域的美观程度是多少,你能帮帮他吗?

输入格式

第一行三个正整数 n,m,k(1n,m100,1k1000)n,m,k(1\le n,m\le 100,1\le k\le 1000),其中 n,mn,m 表示矩形区域的大小,kk 表示树的类型总数。

接下来 nn 行,每行 mm 个正整数,其中第 ii 行第 jj 列为 ci,j(1ci,jk)c_{i,j}(1\le c_{i,j}\le k),表示树的类型。

接下来 kk 行,每行 kk 个非负整数,其中第 ii 行第 jj 列为 Mi,j(0Mi,j109)M_{i,j}(0\le M_{i,j}\le 10^9),表示协调系数矩阵。保证 i[1,k],Mi,i=0\forall i\in[1,k],M_{i,i}=0

输出格式

输出一个非负整数,表示矩形区域的美观程度。

样例

输入样例 1:

2 2 3
1 2
3 1
0 2 3
4 0 6
7 8 0

输出样例 1:

32

输入样例 2:

4 5 8
1 2 4 7 6
2 3 5 1 3
5 2 1 4 7
7 6 3 1 4
0 78 21 45 66 22 991 45
19 0 1 4 617 322 91 45
21 78 0 45 636 22 991 0
45 78 21 0 66 22 91 1
7 78 21 45 0 22 3 0
91 78 21 45 6 0 921 45
26 78 21 45 566 22 0 88
0 0 1 0 5 0 4 0

输出样例 2:

21380