阿Q被困在了一个 $n \times m$ 的迷宫里，他想知道能否在 t 秒内到达迷宫出口（到达时间小于 t），如果可以，最短时间是多少？

迷宫表示为 $n \times m$ 个格子，格子中字符为'@'的是阿Q目前的位置，字符为'$'的是迷宫的出口，字符为'.' 的表示路，字符为'#'的表示墙，不能通过，字符为'A'到'J'的是门，只有有对应的钥匙才可以通过，对应的钥匙为'a' 到'j'，字符为'a' 到'j'的表示到达这个格子可以得到这把钥匙。迷宫只有一个出口。

输入格式

第一行输入三个整数 $n,m,t（1\leq n,m\leq 20,1 \leq t \leq 100）$，表示迷宫格子的行数和列数。 接下来 n 行，每行 m 个字符表示迷宫的情况。

输出格式

输出一行，包含一个整数，如果阿Q可以在时限内到达，输出最少的时间，否则输出-1。 输出时每行末尾的多余空格，不影响答案正确性 要求使用「文件输入输出」的方式解题，输入文件为 maze.in，输出文件为 maze.out

样例输入

2 3 5
@A$
.a#

样例输出

4