题目描述

有一个 $N\times M$ 的网格，第 $(i,j)$ 个格子的高度为 $h_{i,j}$。部分格子是跳水点。

对于一个跳水点，定义它的趣味值为最小的非负整数 $C$，使得从该点出发，每次走到上下左右相邻的格子且相邻两格高度差的绝对值不超过 $C$ 时，能够到达至少 $T$ 个不同格子。

求所有跳水点的趣味值之和。

输入格式

第一行包含三个整数 $N,M,T$。

接下来 $N$ 行，每行包含 $M$ 个整数，表示各格子的高度。

再接下来 $N$ 行，每行包含 $M$ 个整数。$1$ 表示该格是跳水点，$0$ 表示不是。

输出格式

输出一个整数。

3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1

24

数据范围与提示

• $1 \le N,M \le 500$
• $1 \le T \le NM$
• $0 \le h_{i,j} \le 10^9$