描述

巫师KM经常忘记关闭门。
所以他发明了一扇用魔法咒语打开并在一段时间后自动关闭的魔法门。
他在他的房子里放了很多门，所以移动起来变得非常困难。
他想知道在他的房子里两个地方之间移动的最短时间，所以他施了一个魔法咒语把你召唤过来，你是一个优秀的程序员。
KM的房子由一个方形单元格矩阵组成。一个单元格可以是以下之一。

. 空白
# 墙
^ 起点
$ 终点
a-h 魔法圆圈
A-H 魔法门
```他可以在一秒钟内移动一个单元格到它的4个邻居单元格。  
他可以进入空白单元格、起点、终点、魔法圆圈和已打开的魔法门。  
房子被墙壁包围，所以他不能走出去。  
在魔法圆圈上，他可以消耗任意数量的MP（魔法能量）施展魔法咒语。这需要一秒钟的时间。当他使用x个MP时，相应的魔法门在x秒钟内打开。  
他可以进入在那个时间关闭的门。  
可能会有多个相同的魔法圆圈或相同的魔法门。在这种情况下，当他在任何魔法圈上施展魔法咒语时，所有相应的魔法门都会打开。  
在开始时，他的MP为0。他可以在任意时刻进行冥想并恢复MP。每1点MP需要一秒钟的时间。没有MP的上限。  
找到从起点到终点的最短时间。

* * *

### 输入

输入文件的第一行包含两个整数$H$和$W$（$1 \leq H, W \leq 30$）。  
接下来的$H$行，每行包含$W$个字符$\\{c_{ij}\\}$，描述了KM的房子的地图。  
每个字符$c_{ij}$是以下字母之一：`。`，`#`，`^`，`$`，`a`\-`h`，`A`\-`H`。  
地图中只有一个起点和一个终点。

### 输出

以秒为单位输出最短时间。  
如果无法到达目标，则输出`-1`。

* * *

### 示例输入

```plain

1 3
^.$

示例输出

2

示例输入

1 4
^aA$

示例输出

5

示例输入

1 4
^aB$

示例输出

-1

示例输入

3 3
^AB
a#A
b#$

示例输出

19

来源名称

第一届KMCMonthly比赛