题目描述

年轻的冒险家鲍勃·贝内特找到了猩猩岛宝藏的地图，邪恶的加勒比海盗LeChimp将宝藏藏在Zimbu纪念纪念碑(ZM2)内。ZM2由多条走廊组成的迷宫构成。为了保护宝藏，LeChimp在走廊中放置了多个石块阻挡道路。地图上标注了每个石块的硬度，这决定了摧毁石块所需的时间。

ZM2边界有多个入口门，鲍勃可以从这些门进入走廊。幸运的是，某些入口门处可能存放有炸药包，如果鲍勃从这些门进入，可以携带炸药包。每个炸药包含有若干炸药，可以大幅缩短摧毁石块的时间。一旦进入，鲍勃不能离开ZM2后再次进入，也不能走到其他入口门区域（因此他不能携带超过一个炸药包）。

石块的硬度为1到9的整数，表示摧毁该石块所需的天数。在走廊中移动的时间可以忽略不计。使用炸药可以瞬间摧毁一个石块，其时间也可以忽略。问题在于找出鲍勃到达宝藏所需的最短时间。他可以选择任意一个入口门进入ZM2。

输入

输入包含多个测试用例。每个测试用例包含从上方查看的ZM2地图。地图是一个由字符组成的矩形矩阵。鲍勃可以向上、下、左、右四个方向移动，但不能斜向移动。他不能进入用星号(*)表示的区域，即使使用所有炸药也不行！字符($)表示宝藏的位置。数字字符(1到9)表示硬度等于该数字的石块。仅出现在地图边界的井号(#)表示没有炸药包的入口门。边界上的大写字母表示带有炸药包的入口门，字母A表示包中有1个炸药，B表示2个炸药，以此类推。地图边界上的其他所有字符都是星号。走廊用点(.)表示。每个测试用例后有一个空行。地图的宽度和高度至少为3，最多为100个字符。输入的最后一行包含两个连字符(--)。

输出

对于每个测试用例，输出一行数字表示鲍勃到达宝藏所需的最少天数，如果可能到达的话。如果无法到达宝藏，输出IMPOSSIBLE。

输入样例1

*****#*********
*.1....4..$...*
*..***..2.....*
*..2..*****..2*
*..3..******37A
*****9..56....*
*.....******..*
***CA**********

*****
*$3**
*.2**
***#*

--

输出样例1

1
IMPOSSIBLE

来源

2006年德黑兰区域赛