题目描述

冬季 Moolympics 运动会的越野滑雪场地被描述为一个 $M\times N(1\le M,N\le 500)$ 的网格，每个海拔的数值在 $0$ 到 $10^9$ 之间。

网格中的一些格子被标记为该场地的起点。Moolympics 的组织者想要为每个格子设定一个难度评级。一个起点 $P$ 的难度评级是最小的整数 $D$，满足当一头奶牛从 $P$ 出发，在只能到达相邻的格子，且此格子与当前格子的海拔之差的绝对值不超过 $D$ 才能前往的情况下，至少能到达 $T(1\le T\le M\times N)$ 个格子。两个格子相邻当且仅当一个格子向北、向南、向东或向西走能直接到达另一个格子。

请帮助组织者们为每个起点计算难度评级。

输入格式

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

接下来 $M$ 行，每行输入 $N$ 个整数，表示海拔。

接下来 $M$ 行，每行输入 $N$ 个整数，每个整数为 $0$ 或 $1$，为 $1$ 则表示此网格是一个起点。

输出格式

输出一行一个整数，表示所有起点的难度评级的和（注意到每一个难度评级都在 32-bit 整数的范围内，但是难度评级的和可能不在此范围中）。

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 

提示

滑雪场地被描述为一个 $3\times 5$ 的海拔网格，左上角和右下角的格子被标记为起点。对于每一个起点，我们要能够到达至少 $10$ 个格子。

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