~mitsuha ~mitsuha ~mitsuha， 小雅米还是忘不了那个人的名字
有一天在梦中，小雅米梦到了彗星将砸向 mitsuha 所处的糸守町。小雅米为了拯救 mitsuha，不惜背着 ddc 寻找通往那个世界的道路，最终她来到了一个迷宫，迷宫的终
点是通向 mitsuha 所在世界的传送门，小雅米从 (1,1) 开始，每天可以向上下左右移动一格。迷宫中有 k 种钥匙，必须集齐k种钥匙才能打开最终的传送门。同时，迷宫中充斥着怪物和障碍物。怪物一共k种，每种怪物对应了一种钥匙，如果你要从他的位置走过且身上带有对应的钥匙，则必须交出一把对应的钥匙(如没有携带对应钥匙则可以直接通过，携带了对应钥匙必须交出对应钥匙)。障碍物不可通过。由于 ddc 和小雅米心意相通，他知道小雅米要来这个地方，但并不知道小雅米的意图，如果知道了，ddc 会立马和小雅米分手。小雅米为了不让 ddc 怀疑，如果碰到 ddc，必须和 ddc 原地呆三天，表达爱意以消除 ddc 的疑虑。但为了赶上彗星来到的时间，小雅米希望能尽快集齐钥匙达到传送门，请你帮小雅米算一算，她最快要走多久才能集齐钥匙达到传送门。
注：一个地方的钥匙可以重复拿，但同种钥匙每次身上只能携带一把。
第一行输入两个整数 n(1≤n≤20)，m(1≤m≤20)，k(1≤k≤5)。n, m 表示迷宫一共 n 行 m 列， k 表示一共有 k 种钥匙。
接下来 n 行，每行m 个字符，表示迷宫:
"." 表示可以通过"*" 表示障碍物"$" 表示传送门数字表示钥匙种类, 如 "0"，钥匙编号 x(0≤x≤k−1)。
大写字母表示怪物, 如 "A", (字符对应ASCII编码 - "A"对应ASCII编码)的值表示对应钥匙的编号。
"d" 表示 ddc。
输出一个整数，表示小雅米最短需要多少天能集齐钥匙并达到传送门处。如果不能到达则输出 "-1"。
3 3 1
..0
.*.
..$
4