该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

今天你被老师劳务派遣支援到位于南部某出海口的 □□游戏 帮助他们为新版本做QA，你的任务是测试该公司一个新人员工制作的小游戏模块，你打开一看，不由得惊呼“地图设计太烂了！”

游戏是一个二维迷宫，我们用一个包含以下字符的网格表达它：

• '.' 代表一个空房间
• '#' 代表一堵墙
• '@' 是起点
• 小写字母代表钥匙
• 大写字母代表锁

该游戏引以为傲的高机动特性在这个迷宫中荡然无存，玩家每次操作只能让团子一样的角色向前后左右四个方向移动一格，不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，系统会自动拾取这把钥匙。除非玩家手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

糟糕的地图设计使得用户往往需要大量的移动才能获取所有的钥匙，甚至有的地图根本不可能获取所有的钥匙，作为一个QA，你需要找到获取所有钥匙所需要的最少移动次数。

Format

Input

第一行两个数字m，n，分别表示地图的宽和高

接下来的n行每行m个字母，表示地图的信息 （m , n均小于50）

Output

一个整数，获取完所有钥匙需要的最少步数，如果不可能获取所有钥匙，输出-1

Samples

Sample 1

5 3
@.a..
###.#
b.A.B

8

图例：

注意，不需要打开所有的锁

.

Sample 2

3 1
@Aa

-1

图例：

Limitation

1s, 1024KiB for each test case. 0 */