#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
const int MAXN = 805;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int n, s;
pair<int, int> mecho, home;
queue<pair<int, int>> q;
char grid[MAXN][MAXN];
int depth[2][MAXN][MAXN];
bool bbound(int x, int y){
return (x >= 0 && y >= 0 && x < n && y < n && (grid[x][y] == 'G' || grid[x][y] == 'H' || grid[x][y] == 'M'));
}
bool mbound(int x, int y){
return (x >= 0 && y >= 0 && x < n && y < n && (grid[x][y] == 'G' || grid[x][y] == 'M' || grid[x][y] == 'D'));
}
bool check(int lim){
if(depth[0][mecho.first][mecho.second] <= lim) return false;
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) depth[1][i][j] = 0;
depth[1][mecho.first][mecho.second] = 1;
while(!q.empty()) q.pop();
q.push(mecho);
while(!q.empty()){
pair<int, int> curr = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int x = curr.first + dx[i];
int y = curr.second + dy[i];
int d = depth[1][curr.first][curr.second] + 1;
// cout << d << '\n';
if(mbound(x, y) && !depth[1][x][y]){
// cout << d << '\n';
if((d - 1) / s + 1 + lim <= depth[0][x][y]){
depth[1][x][y] = d;
q.push(make_pair(x, y));
}
if(x == home.first && y == home.second && (d - 1) / s + lim - ((d-1) % s == 0) <= depth[0][x][y]) return true;
}
}
}
return depth[1][home.first][home.second];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> s;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> grid[i][j];
if(grid[i][j] == 'H') {
q.push(make_pair(i, j));
depth[0][i][j] = 1;
}
else if(grid[i][j] == 'M') mecho = make_pair(i, j);
else if(grid[i][j] == 'D') home = make_pair(i, j);
}
}
while(!q.empty()){
pair<int, int> curr = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int x = curr.first + dx[i];
int y = curr.second + dy[i];
if(bbound(x, y) && !depth[0][x][y]){
depth[0][x][y] = depth[0][curr.first][curr.second] + 1;
q.push(make_pair(x, y));
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) {
// depth[1][i][j] = (depth[1][i][j] + s - 1) / s;
depth[0][i][j] -= (depth[0][i][j] > 0);
}
}
depth[0][home.first][home.second] = 1e9;
int low = -1, high = 1e9;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (check(mid)) low = mid;
else high = mid - 1;
}
cout << (low) << '\n';
// cout << check(1) << '\n';
// for(int i = 0; i < n; i++){
// for(int j = 0; j < n; j++){
// cout << depth[0][i][j] << ' ';
// }
// cout << " ";
// for(int j = 0; j < n; j++){
// cout << depth[1][i][j] << ' ';
// }
// cout << '\n';
// }
return 0;
}
