题目描述

滑雪场用一个$\red{M×}$$\red{N(1 <= M,N <= 500)}$的数字矩阵表示海拔高度，每个数字表示一个范围在$\red{0 .. 1,000,000,000}$的高度。

有些格子被指定为起点，组织者想对这些起点做难度评级。

如果起点$\red{P}$点是一个难度级别为$\red{D}$的起点，则$\red{D}$必须是满足以下条件的一个最小值：

$\red{（1）}$从一个格子只能滑到相邻的格子；

$\red{（2）}$这两个格子的海拔差不超过$\red{D}$；

$\red{（3）}$至少能够到达$\red{T（}$$\red{1 <= T <= M×}$$\red{N）}$个格子（包括起点本身）。

请帮助主办单位计算每个起点的难度等级。

输入格式

第$\red{1}$行:整数$\red{M}$、$\red{N}$和$\red{T}$。

第$\red{2 . .1+M}$行:这$\red{M}$条线中的每一条都包含$\red{N}$个整数高程。

第$\red{2 + M. .1+2M}$行:每$\red{M}$行包含$\red{N}$个值，$\red{0}$或$\red{1,1}$表示一个单元格作为起点。

输出格式

第$\red{1}$行:所有起始点的难度评级总和

(注意，这可能不适合$\red{32}$位整数，即使单个难度评级可以)。

样例

输入样例

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

提示

滑雪场地用$\red{3 ×}$ $\red{5}$的网格来描述。左上角和右下角的单元格被指定为起点。

从每个起点开始，我们必须能够到达至少$\red{10}$个细胞。

左上起始点的难度等级是$\red{4，}$右下起始点的难度等级是$\red{20}$。