C. 你的名字

~mitsuha ~mitsuha ~mitsuha， 小雅米还是忘不了那个人的名字

有一天在梦中，小雅米梦到了彗星将砸向 mitsuha 所处的糸守町。小雅米为了拯救 mitsuha，不惜背着 ddc 寻找通往那个世界的道路，最终她来到了一个迷宫，迷宫的终

点是通向 mitsuha 所在世界的传送门，小雅米从 $(1,1)$ 开始，每天可以向上下左右移动一格。迷宫中有 $k$ 种钥匙，必须集齐k种钥匙才能打开最终的传送门。同时，迷宫中充斥着怪物和障碍物。怪物一共k种，每种怪物对应了一种钥匙，如果你要从他的位置走过且身上带有对应的钥匙，则必须交出一把对应的钥匙(如没有携带对应钥匙则可以直接通过，携带了对应钥匙必须交出对应钥匙)。障碍物不可通过。由于 ddc 和小雅米心意相通，他知道小雅米要来这个地方，但并不知道小雅米的意图，如果知道了，ddc 会立马和小雅米分手。小雅米为了不让 ddc 怀疑，如果碰到 ddc，必须和 ddc 原地呆三天，表达爱意以消除 ddc 的疑虑。但为了赶上彗星来到的时间，小雅米希望能尽快集齐钥匙达到传送门，请你帮小雅米算一算，她最快要走多久才能集齐钥匙达到传送门。

注：一个地方的钥匙可以重复拿，但同种钥匙每次身上只能携带一把。

第一行输入两个整数 $n(1\leq n\leq 20)$，$m(1\leq m\leq 20)$，$k(1\leq k\leq 5)$。$n,\ m$ 表示迷宫一共 $n$ 行 $m$ 列， $k$ 表示一共有 $k$ 种钥匙。

接下来 $n$ 行，每行$m$ 个字符，表示迷宫:

• "." 表示可以通过
• "*" 表示障碍物
• "$" 表示传送门

数字表示钥匙种类, 如 "0"，钥匙编号 $x(0\leq x\leq k - 1)$。

大写字母表示怪物, 如 "A", (字符对应ASCII编码 - "A"对应ASCII编码)的值表示对应钥匙的编号。

"d" 表示 ddc。

输出一个整数，表示小雅米最短需要多少天能集齐钥匙并达到传送门处。如果不能到达则输出 "-1"。

样例输入1

3 3 1
..0
.*.
..$

样例输出1

4