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, s;
private static char[][] grid;
private static int[][] bees;
private static int[] start, end;
private static boolean valid(int x, int y){
return 0 <= x && x < n && 0 <= y && y < n;
}
private static boolean check(int x){
if(bees[start[0]][start[1]] <= x){
return false;
}
boolean[][] dist = new boolean[n][n];
Queue<int[]> cur = new LinkedList<>();
cur.add(new int[]{start[0], start[1], 0});
dist[start[0]][start[1]] = true;
while(!cur.isEmpty()){
int[] z = cur.poll();
for (int i = 0; i < 4; i++) {
int fx = z[0] + dx[i];
int fy = z[1] + dy[i];
if(valid(fx, fy) && !dist[fx][fy] && grid[fx][fy] != 'T' && (z[2] + 1)/s + x < bees[fx][fy]){
dist[fx][fy] = true;
cur.add(new int[]{fx, fy, z[2] + 1});
}
}
}
return dist[end[0]][end[1]];
}
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()); s = Integer.parseInt(st.nextToken());
grid = new char[n][n];
start = new int[]{-1, -1}; end = new int[]{-1, -1};
Queue<int[]> hives = new LinkedList<>();
bees = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(bees[i], Integer.MAX_VALUE);
}
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});
bees[i][j] = 0;
}
grid[i][j] = str.charAt(j);
}
}
while(!hives.isEmpty()){
int[] x = hives.poll();
for (int i = 0; i < 4; i++) {
int fx = x[0] + dx[i];
int fy = x[1] + dy[i];
if(valid(fx, fy) && bees[fx][fy] == Integer.MAX_VALUE && (grid[fx][fy] == 'G' || grid[fx][fy] == 'M')){
bees[fx][fy] = x[2] + 1;
hives.add(new int[]{fx, fy, x[2] + 1});
}
}
}
int left = 0;
int right = n * n;
while(left < right){
int mid = left + (right - left + 1)/2;
if(check(mid)){
left = mid;
}
else{
right = mid - 1;
}
}
if(check(right)){
pw.println(right);
}
else{
pw.println(-1);
}
pw.close();
}
}
