E - Magic Doors
Editorial
/

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.

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

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

Find the shortest time to move from the start to the goal.

The first line of the input file contains two integers

Subsequent

Each character

There is only one start and one goal in the map.
Output the shortest time by the second.

If it is impossible to reach the goal, output

Time Limit: 1.5 sec / Memory Limit: 93 MB

### Description

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 doorHe 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

`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

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