#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
#define int long long int
#define pb push_back
#define mid (l+(r-l)/2)
#define f first
#define s second
static const int N=805;
static const int MOD=(1LL<<61)-1;
static const int inf=INT64_MAX;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
void io(string name = ""){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
int n,s,mx,my,hx,hy;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
vector<vector<char>>v(N,vector<char>(N));
bool inside(int i,int j){ return ((i>0&&i<=n) && (j>0&&j<=n) && (v[i][j]=='M' || v[i][j]=='G'));}
int32_t main(){
//io("local");
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>s;
vector<array<int,2>>h;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>v[i][j];
if(v[i][j]=='M'){mx=i,my=j;}
if(v[i][j]=='D'){hx=i,hy=j;}
if(v[i][j]=='H'){h.pb({i,j});}
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<bee[i][j]<<" ";
// }cout<<endl;
// }
int l=0,r=n*n;
bool aaa=0;
while(l<=r){
vector<vector<int>>mec(N,vector<int>(N));
vector<vector<bool>>vis(N,vector<bool>(N));
vector<vector<bool>> vis2(N, vector<bool>(N));
vector<vector<int>> bee(N, vector<int>(N));
queue<array<int,2>> q;
for(auto i:h) {
q.push({i[0],i[1]});
vis2[i[0]][i[1]] = 1;
}
while(!q.empty()) {
int x=q.front()[0], y=q.front()[1];
q.pop();
for (int i=0;i<4;i++) {
int nx=x+dx[i], ny=y+dy[i];
if (inside(nx,ny) && !vis2[nx][ny]) {
bee[nx][ny]=bee[x][y] + 1;
q.push({nx,ny});
vis2[nx][ny]=1;
}
}
}
vis[mx][my]=1;
q.push({mx,my});
if(bee[mx][my]<=mid){q.pop();}
while(q.size()){
array<int,2>c=q.front();
q.pop();
for(int i=0;i<4;i++){
int cx=c[0]+dx[i],cy=c[1]+dy[i];
// cout<<c[2]/s<<" ";
if(inside(cx,cy) && !vis[cx][cy] && (mec[c[0]][c[1]]+1)/s < bee[cx][cy]-mid){
vis[cx][cy]=1;
mec[cx][cy]=mec[c[0]][c[1]]+1;
q.push({cx,cy});
}
}
}
bool chc=0;
for(int i=0;i<n;i++){
int cx=hx+dx[i],cy=hy+dy[i];
if(inside(cx,cy) && mec[cx][cy]/s<bee[cx][cy] && vis[cx][cy]){chc=1;aaa=1;}
}
// cout<<mid<<" "<<chc<<endl;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<mec[i][j]<<" ";
// }cout<<endl;
// }
if(chc){l=mid+1;}
else{r=mid-1;}
}
if(aaa){cout<<l-1;}
else{cout<<-1;}
return 0;
}
