E - Magic Doors Editorial /

Time Limit: 1.5 sec / Memory Limit: 93 MB

Description

Wizard KM often forgets to close doors.
So he invented the magic door which opens with a magic spell and automatically closes after a while.
He put the doors in many places in his house, so it became very difficult to move around.
He wants to know the shortest time to move between two places in his house, so he cast a magic spell and summoned you, the excellent programmer.
KM's house consists of a matrix of square cells. A cell is one of the followings.
. empty
# wall
^ start
$ goal
a-h magic circle
A-H magic door
He can move one cell to its 4-neighborhood in a second.
He can move into empty cells, start, goal, magic circles, and opened magic doors.
The house is surrounded by the walls, so he can't go out.
On a magic circle, he can cast a magic spell by consuming arbitrary amount of MP (Magic power). This takes a second. When he uses x MP, the corresponding magic doors opens during x seconds.
He can move into a door which closes at that time.
There may be more than one same magic circles or same magic doors. In this case, all the corresponding magic doors opens when he cast a magic spell on any magic circles.
At the beginning, his MP is 0. He can meditate at arbitrary timing and restore MP. Meditation takes a second per 1 MP. There is no upper bound of MP.
Find the shortest time to move from the start to the goal.

Input

The first line of the input file contains two integers H and W (1 \leq H, W \leq 30).
Subsequent H lines of W characters \{c_{ij}\} are the map of KM's house.
Each character c_{ij} is one of the letters ., #, ^, $, a-h, A-H.
There is only one start and one goal in the map.

Output

Output the shortest time by the second.
If it is impossible to reach the goal, output -1 instead.

Sample Input

1 3
^.$

Sample Output

2

Sample Input

1 4
^aA$

Sample Output

5

Sample Input

1 4
^aB$

Sample Output

-1

Sample Input

3 3
^AB
a#A
b#$

Sample Output

19

Source Name

The First KMCMonthly Contest