침프 섬의 보물

젊은 모험가 밥 베넷은 침프 섬의 보물 지도를 손에 넣었다. 악명 높은 유령 좀비 해적 르침프가 여러 복도가 얽혀 미로를 이루는 짐부 기념비(ZM2) 어딘가에 보물을 숨겨 두었다. 보물을 지키기 위해 르침프는 복도 곳곳에 돌덩이를 놓아 보물로 가는 길을 막아 두었다. 각 돌덩이에는 단단함이 정해져 있으며, 이는 그 돌을 부수는 데 걸리는 날수를 뜻한다.

ZM2의 경계에는 여러 개의 출입구가 있어 밥은 그중 하나로 들어갈 수 있다. 운 좋게도 일부 출입구에는 다이너마이트 묶음이 놓여 있어, 그런 출입구로 들어가면 밥은 그 묶음을 챙길 수 있다. 다이너마이트를 쓰면 돌덩이를 순식간에 부술 수 있다. 한 번 안으로 들어가면 밥은 밖으로 나갔다가 다시 들어올 수 없고, 다른 출입구가 있는 칸을 밟을 수도 없다(그래서 다이너마이트 묶음은 최대 하나만 챙길 수 있다).

돌덩이의 단단함은 1 이상 9 이하의 정수이며, 그 돌을 맨손으로 부수는 데 필요한 날수와 같다. 복도를 이동하는 시간과 다이너마이트로 돌을 부수는 시간은 모두 무시한다. 밥이 보물에 도달하는 데 걸리는 최소 날수를 구하여라. 밥은 어느 출입구로든 들어갈 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 ZM2를 위에서 내려다본 지도이며, 문자로 이루어진 직사각형 행렬이다. 밥은 상하좌우 네 방향으로 움직일 수 있으나 대각선으로는 움직일 수 없다. 각 문자의 뜻은 다음과 같다.

• * : 벽. 다이너마이트를 모두 써도 들어갈 수 없다.
• $ : 보물의 위치.
• 1~9 : 그 숫자와 같은 단단함을 가진 돌덩이.
• # : 다이너마이트가 없는 출입구. 지도의 경계에만 나타난다.
• 경계에 있는 대문자 : 다이너마이트 묶음이 있는 출입구. A는 다이너마이트 1개, B는 2개처럼 알파벳 순서대로 개수가 늘어난다.
• . : 복도.

경계에 있는 그 밖의 모든 문자는 *이다. 지도의 너비와 높이는 각각 3 이상 100 이하이다. 각 테스트 케이스 뒤에는 빈 줄이 하나 있다. 입력의 마지막 줄에는 붙임표 두 개 --가 있다.

각 테스트 케이스마다, 밥이 보물에 도달하는 데 걸리는 최소 날수를 한 줄에 하나씩 출력한다. 보물에 도달할 수 없으면 IMPOSSIBLE을 출력한다.