Treasure of Chimp Island

Bob Bennett, a young adventurer, has found the map to the treasure of Chimp Island. The infamous ghost-zombie pirate LeChimp hid the treasure somewhere inside the Zimbu Memorial Monument (ZM2), a maze of corridors. To guard it, LeChimp placed stone blocks throughout the corridors to bar the way. Each block has a hardness that tells how many days it takes to break by hand.

ZM2 has several gates on its boundary, and Bob may enter through any one of them. Luckily, some gates hold a pack of dynamite; entering through such a gate lets Bob take the pack with him, and dynamite destroys a block instantly. Once inside, Bob can neither leave and re-enter nor step onto the cell of another gate, so he can pick up at most one pack of dynamite.

Each block's hardness is an integer from 1 to 9, equal to the number of days needed to break it by hand. Time spent walking through corridors and time spent breaking a block with dynamite are both ignored. Find the minimum number of days in which Bob can reach the treasure, given that he may choose any gate to enter.

The input consists of several test cases. Each test case is a top-down map of ZM2, given as a rectangular matrix of characters. Bob moves in the four directions up, down, left, and right, but never diagonally. The characters mean:

• * : a wall that cannot be entered even with all of Bob's dynamite.
• $ : the treasure.
• 1-9 : a stone block whose hardness equals the digit.
• # : a gate without dynamite; it appears only on the boundary of the map.
• an uppercase letter on the boundary : a gate holding a pack of dynamite. A means one stick, B two sticks, and so on through the alphabet.
• . : a corridor.

Every other character on the boundary is *. The width and height of the map are each at least 3 and at most 100. A blank line follows each test case. The last line of the input contains two dashes --.

For each test case, print on its own line the minimum number of days Bob needs to reach the treasure. If the treasure cannot be reached, print IMPOSSIBLE.