#P2266. 爱的供养

爱的供养

题目背景

在很久很久以前,有一只野心勃勃的骑士 Mori,带领自己的军队,征战世界,所向披靡……

有一天,他跨过千山万水,越过重重山岭,来到了一个美丽的(程序)国度。在这里,他与 Soha 公主一见钟情,并最终坠入爱河。

从此,他们幸福快乐地生活在了一起……

题目描述

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

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

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

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

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

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

输入格式

11 行,三个整数 MMNNTT

接下来 MM 行,每行 NN 个整数,为各格的高度。

接下来 MM 行,每行 NN001111 代表该格点埋藏有钥匙。

输出格式

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

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

提示

1M,N6001 ≤ M, N ≤ 600

1TM×N1 ≤ T ≤ M\times N