我们要从迷宫的起点 S 走到终点 E，每一步我们只能选择上下左右四个方向中的一个前进一格。 W 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 D 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 K 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 . 则是代表空无一物的地方，欢迎自在的游荡。

本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。

请问，从起点到终点，最少要走几步呢？

输入的第一行有两个正整数 $H, W$，分别代表迷宫的长跟宽。

接下来的 $H$ 行代表迷宫，每行有一个长度恰为 $W$ 的字串，此字串只包含 S,E,W,D,K,. 这五种字元。