A3172 | 剑之试炼

时间限制：2000ms

内存限制：512MB

*只有兼具「力量」、「智慧」与「勇气」才能成为真正的勇者。*

---

「林克」想要提升「大师之剑」的实力，必须通过「剑之试炼」。

「剑之试炼」共有 $K$ 层「地下试炼场」，每层试炼场 $i$ 使用一个 $N \times M$ 的字符网格 $grid_i$ 来表示。

对于每层试炼场，第 $i$ 层有若干「障碍物」（使用字符 # 表示），「空地」（使用字符 . 表示），以及 $X_i$ 只「波克布林」。

「林克」如果想要从地下 $i$ 层前往地下 $i + 1$ 层，则需要使用 「大师之剑」击败地下 $i$ 层的全部 $X_i$ 只「波克布林」。

「波克布林」共有 $5$ 个品种，「林克」可以使用「大师之剑」击败波克布林，每次攻击需要 $1$ 秒，每次攻击可以扣除任意品种的「波克布林」 $30$ 点血量；

「波克布林」的品种及其他信息如下表所示：



「林克」可以在「地下试炼场」中 上下左右 移动，但不能越过试炼场边界或者是移动到有障碍物的格点。

更正式地：令「林克」在地下 $i$ 层的试炼场 $grid$ 上的当前位置为 $(x, y)$，那么可以消耗 $1$ 秒，移动到 $(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)$ 四个位置中的一个。令 $(x', y')$ 为移动后的位置，则要求 $grid_{x', y'} \ne$ #。

若移动后的位置上有「波克布林」则需要消耗一定的时间（具体查看上表）将其击败后才可以继续行动。

在击败地下 $i$ 层的所有「波克布林」后，「林克」依然可以在地下 $i$ 层继续移动，以选择任意一处不为「障碍物」的位置，花费 $1$ 秒时间，传送至地下 $i + 1$ 层的对应位置上（要求地下 $i + 1$ 层该位置上必须为「空地」）。
更正式地：令地下 $i$ 层的地图为 $grid$，地下 $i + 1$ 层为 $grid'$；「林克」可以在击败该层的所有「波克布林」后，前往该层的 $(x, y)$ 处，满足 $grid_{x, y} \ne$ # 且 $grid'_{x, y} =$ .；从地下 $i$ 层的 $(x, y)$ 处传送至地下 $i + 1$ 层的 $(x, y)$ 处。

题目保证每层试炼场位置 $(1, 1)$ 处一定没有障碍物和「波克布林」，且可以从 $(1, 1)$ 处到达任何一处「波克布林」所在的位置。

请你计算「林克」从地下 $1$ 层 $(1, 1)$ 处出发，击败 $K$ 层「地下试炼场」上的所有「波克布林」，通过「剑之试炼」需要的最短时间。

$\large{数据范围}$

- $3 \le N, M \le 100$
- $3 \le K \le 20$
- $1 \le X_i \le \min{\{N \times M - 1, 15\}}$
- 对于每层「地下试炼场」$grid$，其仅由字符 . 和 # 以及 $5$ 种「波克布林」的字符标识构成。
- 对于每层「地下试炼场」保证 $S_{1,1} =$ .。

对于每个测试文件格式如下：

$\tt{N\ M\ K}$

$\tt{grid_1}$
$\tt{grid_2}$
$\tt{\vdots}$
$\tt{grid_K}$

每层试炼场 $\tt{grid_i}$ 的格式如下：

$\tt{S_1}$

$\tt{S_2}$

$\tt{\vdots}$

$\tt{S_N}$

对于每个测试文件，输出「林克」通过「剑之试炼」需要的最短时间。