Description

小明一觉醒来发现自己被困在传说中的魔塔,逃离这个迷宫般的魔塔，规则如下,每个迷宫,可视为一个长为 n,宽为 m 的平面(3 <n,m <= 100),当前迷宫可能有恶魔守卫(‘*’来表示)、通往下一层的钥匙(‘K’来表示)、通往下一层的入口(‘D’来表示),小明每次只能向上,下,左,右四个方向行走,每行走一步消耗一个体力值,初始状态在左上角。小明想用最少的体力值通过迷宫,请聪明的你来帮筋疲力竭的他找到花费最少体力的路径。

Format

Input

输入第一行包含两个整数 n,m 代表当前迷宫的长和宽。接下来的 n 行m列代表当前迷宫的情况。

Output

对于输入,如果能够通过当前关卡,输出一个整数,代表最小消耗的体力值,如果不能够通过输出-1。

Samples

4 4
...K
...D
...*
...*

4

Hint