#include <bits/stdc++.h>
using namespace std;
int n,s;
string matrix[805];
int mechox, mechoy,homex,homey;
vector<pair<int,int>> hives;
bool validsquare(int x, int y){
return x>=0 && x<n && y>=0 && y<n && (matrix[x][y] == 'G' || matrix[x][y] == 'M');
}
bool mecho_reached(int mecho_dis, int bees_dis){
return mecho_dis / s < bees_dis;
}
int main()
{
cin >> n >> s;
for(int i = 0;i<n;i++){
cin >> matrix[i];
}
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(matrix[i][j] == 'M'){
mechox = i;
mechoy = j;
}
if(matrix[i][j] == 'D'){
homex = i;
homey = j;
}
if(matrix[i][j] == 'H'){
hives.push_back(make_pair(i,j));
}
}
}
queue<pair<int,int>> q;
vector<vector<bool>> beesvis(n,vector<bool>(n));
vector<vector<int>> beestime(n,vector<int>(n));
for(auto hive: hives){
q.push({hive.first,hive.second});
beesvis[hive.first][hive.second] = true;
}
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0;i<4;i++){
int newx = x+dx[i],newy=y+dy[i];
if(validsquare(newx,newy) && !beesvis[newx][newy]){
beestime[newx][newy] = beestime[x][y]+1;
q.push({newx,newy});
beesvis[newx][newy] = true;
}
}
}
int l = 0, r = n*n;
while(l<=r){
vector<vector<bool>> mechovis(n,vector<bool>(n));
vector<vector<int>> mechotime(n,vector<int>(n));
queue<pair<int,int>> q2;
int mid = (l+r)/2;
q2.push({mechox,mechoy});
mechovis[mechox][mechoy] = true;
if(beestime[mechox][mechoy] <= mid){
q2.pop();
}
while(!q2.empty()){
int x = q2.front().first;
int y = q2.front().second;
q2.pop();
for(int i = 0;i<4;i++){
int newx = x+dx[i],newy=y+dy[i];
if(validsquare(newx,newy) && !mechovis[newx][newy] && mecho_reached(mechotime[x][y] + 1, beestime[newx][newy] - mid)){
mechotime[newx][newy] = mechotime[x][y]+1;
q2.push({newx,newy});
mechovis[newx][newy] = true;
}
}
}
bool good = false;
for(int i = 0;i<4;i++){
int nx = homex+dx[i],ny = homey+dy[i];
if(validsquare(nx,ny) && mechovis[nx][ny] && mecho_reached(mechotime[nx][ny],beestime[nx][ny]-mid)){
good = true;
break;
}
}
if(good){
l = mid+1;
}
else{
r = mid-1;
}
}
cout << l-1 << endl;
return 0;
}
