import java.io.*;
import java.util.*;
public class mecho {
public static char[][] arr; public static int[][] dis;
public static int num; public static int s;
public static int sx; public static int sy; public static int ex; public static int ey;
public static ArrayDeque<Integer> Hqueue;
public static int[] dx = {0,0,-1,1};
public static int[] dy = {-1,1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer l1 = new StringTokenizer(scan.readLine());
num = Integer.parseInt(l1.nextToken()); s = Integer.parseInt(l1.nextToken());
arr = new char[num][num]; dis = new int[num][num]; Hqueue = new ArrayDeque<>();
for (int i = 0;i<num;i++)
Arrays.fill(dis[i],Integer.MAX_VALUE);
sx = -1; sy = -1; ex = -1; ey = -1;
for (int i = 0;i<num;i++) {
StringTokenizer st = new StringTokenizer(scan.readLine()); String s = st.nextToken();
for (int j = 0;j<num;j++) {
arr[i][j] = s.charAt(j);
if (arr[i][j]=='M') {
sx = i; sy = j;
} else if (arr[i][j]=='D') {
ex = i; ey = j;
} else if (arr[i][j]=='H') {
Hqueue.add(i*num+j);
dis[i][j] = 0;
}
}
}
bfsH();
int low = 0; int high = num;
while (low<high) {
int mid = (low+high+1)/2;
if (bfsB(mid)) {
low = mid;
} else {
high = mid-1;
}
}
System.out.println(low);
}
public static boolean bfsB (int eat) { //bfs for the bears
ArrayDeque<Pair> bear = new ArrayDeque<>();
bear.add(new Pair(sx*num+sy,eat*s));
boolean[][] visited = new boolean[num][num];
visited[sx][sy] = true;
while (!bear.isEmpty()) {
Pair curr = bear.poll(); int node = curr.node; int time = curr.time;
int x = node/num; int y = node%num;
//int minute = time/s; int sec = time%s;
for (int i = 0;i<4;i++) {
int nx = x+dx[i]; int ny = y+dy[i];
if (nx<0||ny<0||nx>=num||ny>=num||visited[nx][ny]) continue; //||dis[nx][ny]!=Integer.MAX_VALUE
if (arr[nx][ny]=='T'||arr[nx][ny]=='H') continue;
if ((time+1)/s<dis[nx][ny]) {
visited[nx][ny] = true;
bear.add(new Pair(nx*num+ny, time+1));
}
}
}
return visited[ex][ey];
}
public static void bfsH () { //bfs for the bees
while (!Hqueue.isEmpty()) {
int curr = Hqueue.poll();
int x = curr/num; int y = curr%num;
for (int i = 0;i<4;i++) {
int nx = x+dx[i]; int ny = y+dy[i];
if (nx<0||ny<0||nx>=num||ny>=num||dis[nx][ny]!=Integer.MAX_VALUE) continue;
if (arr[nx][ny]=='T'||arr[nx][ny]=='D') continue;
dis[nx][ny] = dis[x][y]+1;
Hqueue.add(nx*num+ny);
}
}
}
public static void printMat (int[][] arr) {
for (int i = 0;i<arr.length;i++) {
for (int j = 0;j<arr[0].length;j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
public static class Pair {
int node; int time;
Pair (int node, int time) {
this.node = node; this.time = time;
}
}
}
