题目描述

有一个 $n \times m$ 的迷宫，迷宫中的每个格子是以下四种类型之一：

• #：墙，不能进入；
• .：空地，可以进入；
• S：起点；
• T：终点。

其中，S 和 T 各恰好出现一次，且都视为可通行格子。

除了格子类型外，每个格子 $(x, y)$ 还对应一个整数 $col_{x,y}$。对于可通行格子，这个整数表示该格子的属性，满足 $0 \le col_{x,y} < P$；如果该格子是墙，则对应的整数没有实际作用，可以忽略。

迷宫中还存在一个会随时间变化的环境属性 $p$，它的取值范围同样是 $0 \sim (P - 1)$。初始时，$p = 0$。

小蓝一开始位于起点 S。时间按秒进行。每经过 1 秒，小蓝必须执行恰好一个动作：向上、下、左、右移动一格，或者留在原地不动。移动时不能走出迷宫，也不能进入墙。

在每一秒中，事件按如下顺序发生：

1. 小蓝先执行这一秒的动作；

2. 接着根据这一秒结束时所在格子的属性，与当前环境属性 $p$ 进行比较：

   • 如果两者相同，则这一秒不会受到伤害；
   • 如果两者不同，则这一秒会受到 1 点伤害；

3. 最后更新环境属性：

需要注意的是，小蓝刚开始站在起点时，不会立刻进行伤害判定。第一次判定发生在第一秒动作结束后。若某一秒动作结束后小蓝到达终点 T，则这一秒的伤害仍需正常结算，结算完成后才算到达终点。

此外，小蓝在整个过程中最多可以使用一次技能，也可以不使用。使用技能时，会额外产生 1 的代价，并且可以将当前环境属性 $p$ 直接改为任意一个 $0 \sim (P - 1)$ 之间的值。

整个过程中产生的总代价由两部分组成：

• 每次受到伤害产生的代价；
• 使用技能产生的代价。

现在，请你计算，小蓝从 S 到达 T 的最小总代价。若无法到达终点，输出 -1。

输入格式

第一行包含三个整数 $n, m, P$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示迷宫。

再接下来 $n$ 行，每行包含 $m$ 个整数，表示各个格子的 $col_{x,y}$。

输出格式

输出一个整数，表示最小总代价。若无法到达终点，输出 -1。

3 4 3
S..#
..#.
...T
0 1 2 2
1 2 0 1
2 0 1 2

0

提示

【样例说明】

初始时环境属性 $p = 0$。

先在起点停留 1 秒。此时小蓝所在格子的属性为 0，与当前环境属性相同，所以这一秒不会受到伤害。之后环境属性更新为 1。

接下来依次向下、下、右、右、右移动到终点。每一秒结束时，小蓝所在格子的属性都恰好等于当时参与判定的环境属性，因此整个过程中都不会受到伤害。

同时不使用技能，所以总代价为 0。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le n, m \le 30$，$2 \le P \le 3$。

对于额外 $30\%$ 的评测用例，$2 \le P \le 10$。

对于所有的评测用例，$1 \le n, m \le 300$，$2 \le P \le 100$。