import java.util.*;
import java.io.*;
public class mecho {
private static int[] dx = {-1, 0, 1, 0};
private static int[] dy = {0, -1, 0, 1};
private static int n;
private static char[][] grid;
private static boolean mark(int x, int y, boolean[][] arr){
for (int i = 0; i < 4; i++) {
int fx = x + dx[i];
int fy = y + dy[i];
if(check(fx, fy) && arr[fx][fy] && grid[fx][fy] != 'T'){
return true;
}
}
return arr[x][y];
}
private static boolean check(int x, int y){
return 0 <= x && x < n && 0 <= y && y < n;
}
public static void main(String[] args) throws IOException{
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(r.readLine());
n = Integer.parseInt(st.nextToken()); int s = Integer.parseInt(st.nextToken());
grid = new char[n][n];
int[] start = {-1, -1}; int[] end = {-1, -1};
Queue<int[]> hives = new LinkedList<>();
int ans = -1;
boolean[][][] times = new boolean[2 * n][n][n];
for (int i = 0; i < n; i++) {
String str = r.readLine();
for (int j = 0; j < n; j++) {
if(str.charAt(j) == 'M'){
start = new int[]{i, j};
}
if(str.charAt(j) == 'D'){
end = new int[]{i, j};
}
if(str.charAt(j) == 'H'){
hives.add(new int[]{i, j, 0});
times[0][i][j] = true;
}
grid[i][j] = str.charAt(j);
}
}
for (int i = 1; i < 2 * n; i++) {
for (int j = 0; j < n; j++) {
for (int j2 = 0; j2 < n; j2++) {
if(grid[j][j2] == 'T'){
continue;
}
times[i][j][j2] = mark(j, j2, times[i - 1]);
}
}
}
for (int i = 0; i < 2 * n; i++) {
Queue<int[]> cur = new LinkedList<>();
cur.add(new int[]{start[0], start[1], 0});
boolean[][] visited = new boolean[n][n];
visited[start[0]][start[1]] = true;
for (int j = i; j < 2 * n; j++) {
while(!cur.isEmpty() && Math.ceil(cur.peek()[0]/s) <= j - i){
int[] x = cur.poll();
if(times[j][x[0]][x[1]]){
continue;
}
for (int k = 0; k < 4; k++) {
int fx = x[0] + dx[k];
int fy = x[1] + dy[k];
if(check(fx, fy) && !times[j][fx][fy] && !visited[fx][fy] && grid[fx][fy] != 'T'){
visited[fx][fy] = true;
cur.add(new int[]{fx, fy, x[2] + 1});
}
}
}
}
// for(boolean[] e : visited){
// System.out.println(Arrays.toString(e));
// }
// System.out.println("===");
if(visited[end[0]][end[1]]){
ans = i;
}
}
pw.println(ans);
pw.close();
}
}
