Description

但好日子却不长久。Mori 的手下大将恶魔猎手在此时背叛了他，自立为王，率领深藏在世界之轴的龙族叛变，并掳走了 Soha 公主。Mori 在与恶魔猎手的战斗中，遭遇围杀，被困在一个荒芜人烟的大岛上。但在经过勘探后，他惊喜地发现，Soha 也同时被恶魔猎手关押在这座岛上！

经过精心研究，Mori 发现关押 Soha 的地牢需要若干把钥匙才能打开，而钥匙则被埋藏在一系列的法阵中。凭借着自己的身手与魔力，Mori 是能够破解法阵、获得钥匙的。法阵是一个 $M\times N$ 大小的矩阵，法阵中的每一格都具有自己的高度。其中，有一部分格中埋藏着钥匙，但 Mori 法力不足，无法直接挖取。而他发现，只需从埋藏着钥匙的格子出发向四周的格子走，并在不少于 $T$ 个的独立法阵格子中施法（包括埋藏钥匙的格子本身也要施法），便可挖出钥匙。换句话说，在他每次挖掘钥匙之前，都必须先从埋藏钥匙的格子开始，走过周围的 $T-1$ 个不重复的格子。

虽然 Mori 施法不需要耗费体力，但他在移动的过程中，需要耗费一定量的体力（体育不及格 233）。从一个格子移动到另一个格子中所耗费的体力值为两个格子的高度值之差的绝对值。

对于每个埋藏钥匙的格子来说，定义其难度值 $P$ 为在施法过程中，每次在各个格子间移动的所需耗费的体力的最大值。

而 Mori 则希望让这个难度值越小越好。因为，只有保留足够多的体力，他才能营救 Soha，并两人合力打败恶魔猎手的背叛。

所以，他想知道所有埋藏钥匙的点的难度值的和最小值可以是多少？

Input Format

第 $1$ 行，三个整数 $M$、$N$、$T$。

接下来 $M$ 行，每行 $N$ 个整数，为各格的高度。

接下来 $M$ 行，每行 $N$ 个 $0$ 或 $1$， $1$ 代表该格点埋藏有钥匙。

Output Format

一个整数，代表难度值的和的最小值。

3 5 5
20 21 20 20 21
19 22 20 60 80
80 90 80 70 90
1 0 0 0 0
0 0 0 0 0
1 0 0 0 1

31

Hint

$1 ≤ M, N ≤ 600$

$1 ≤ T ≤ M\times N$