滑雪场评级

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

一个越野滑雪场地由 $M\times N$ 个格子组成。每个格子有一个海拔值，一些格子被标记为起点。

对于起点 $P$，定义它的难度评级为满足下列条件的最小非负整数 $D$：

奶牛从 $P$ 出发，每次只能移动到上下左右相邻的格子，并且只有当两个格子的海拔差绝对值不超过 $D$ 时才能通过它们之间。按此规则，奶牛至少能够到达 $T$ 个格子。

求所有被标记起点的难度评级之和。

输入格式

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

接下来 $M$ 行，每行包含 $N$ 个整数 $h_{i,j}$，表示各格子的海拔。

接下来 $M$ 行，每行包含 $N$ 个整数 $s_{i,j}$。若 $s_{i,j}=1$，该格子是起点；否则 $s_{i,j}=0$。

输出格式

输出一个整数，表示所有起点的难度评级之和。

单个难度评级在 32 位有符号整数范围内，但总和可能超出该范围。

样例输入 1

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

样例输出 1

24

样例解释

左上角起点的难度评级是 $4$，右下角起点的难度评级是 $20$。

数据范围

对于所有数据：$1\le M,N\le 500$，$1\le T\le MN$，$0\le h_{i,j}\le 10^9$，$s_{i,j}\in\{0,1\}$。