AT_icpc2013summer_warmingUp_e Magic Doors

巫师 KM 经常忘记关门，因此他发明了一种魔法门，可以用魔法咒语开启，并在一段时间后自动关闭。他在房子的许多地方都安装了这种门，以至于他的移动变得非常困难。为了找到在他房子里从一个地方到另一个地方的最短时间，他施法召唤了你，一位优秀的程序员。 KM 的房子由一个矩阵构成，其中每个单元格可能是以下几种情况之一： - `.`：空地 - `#`：墙 - `^`：起点 - `$`：终点 - `a-h`：魔法圈 - `A-H`：魔法门 他可以在一秒钟内移动到相邻的四个方向之一（上、下、左、右）。他可以自由地进入空地、起点、终点、魔法圈以及已经打开的魔法门。而房子被墙壁包围，所以他无法走出房子。 在魔法圈上，KM 可以通过消耗任意数量的 MP（魔法力）施放咒语，这需要一秒。使用 $x$ 点 MP 时，对应的魔法门会保持打开状态 $x$ 秒。即使魔法门正要关闭，他也可以在最后一秒赶进去。 可能会有多个相同的魔法圈或魔法门。在这种情况下，一旦在任意一个魔法圈施法，所有对应的魔法门都会开启。刚开始时，他的 MP 为 0，他可以在任何时候冥想来恢复 MP，每恢复 1 点 MP 需要花费一秒钟，没有上限。 你的任务是找出从起点到达终点的最短时间。

第一行包含两个整数 $H$ 和 $W$，表示房子地图的高度和宽度 ($1 \leq H, W \leq 30$)。接下来的 $H$ 行是房子的地图，包含 $W$ 个字符，每个字符表示房子的一个单元格类型，可能是 `.`, `#`, `^`, `$`, `a-h`, `A-H` 之一。地图中保证只有一个起点和一个终点。

输出从起点到达终点所需要的最短时间（单位：秒）。如果无法到达终点，则输出 -1。 **本翻译由 AI 自动生成**