A29349.剑之试炼

时间限制：2000ms
内存限制：512MB

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

---

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

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

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

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

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

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

品种	地图标记	血量	击败所需时间
红色波克布林	R	13	1秒
蓝色波克布林	B	72	3秒
黑色波克布林	D	240	8秒
白银波克布林	S	720	24秒
黄金波克布林	G	1080	36秒

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

更正式地：令「林克」在地下 $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}$

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

$\bf{样例\ 1：}$

「林克」从地下 $1$ 层 $(1, 1)$ 处出发，前往 $(2, 1)$ 处并击败此处的「红色波克布林」消耗 $2$ 秒，再依次移动到 $(3, 1)$，$(3, 2)$，$(3, 3)$，$(2, 3)$ 处消耗 $4$ 秒，再击败 $(2, 3)$ 处的「蓝色波克布林」消耗 $3$ 秒；此时「林克」击败了地下 $1$ 层的所有「波克布林」；消耗 $1$ 秒移动到 $(3, 3)$ 处，并在此处消耗 $1$ 秒时间传送至地下 $2$ 层。
在地下 $1$ 层一共消耗 $2 + 4 + 3 + 1 + 1 = 11$ 秒。

在地下 $2$ 层 $(3, 3)$ 处出发，依次移动到 $(3, 2)$，$(3, 1)$ 处，消耗 $2$ 秒，并击败 $(3, 1)$ 处的「红色波克布林」消耗 $1$ 秒；此时「林克」击败了地下 $2$ 层的所有「波克布林」，由于地下 $3$ 层的 $(3, 1)$ 处为「空地」，所以「林克」在击败此处的「红色波克布林」后，可以直接传送至地下 $3$ 层的 $(3, 1)$ 处。
在地下 $2$ 层一共消耗 $2 + 1 + 1 = 4$ 秒。

在地下 $3$ 层 $(3, 1)$ 处出发，依次移动到 $(3, 2)$，$(3, 3)$ 处，消耗 $2$ 秒，并击败 $(3, 3)$ 处的「蓝色波克布林」，消耗 $3$ 秒；接下来依次移动到 $(3, 2)$，$(3, 1)$，$(2, 1)$，$(1, 1)$，$(1, 2)$，$(1, 3)$ 处共消耗 $6$ 秒，并消耗 $8$ 秒击败 $(1, 3)$ 处的「黑色波克布林」。
在地下 $3$ 层一共消耗 $2 + 3 + 6 + 8 = 19$ 秒。

至此「林克」击败了「地下试炼场」中的所有「波克布林」。一共消耗 $11 + 4 + 19 = 34$ 秒。无法通过其他方法在更短的时间内通过「剑之试炼」。