#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ins insert
//__builtin_popcount(x);
vector<pair<int,int>>dir={{-1,0},{1,0},{0,1},{0,-1}};//UDRL
const int mod=1e9+7;
int n,s;
char grid[801][801];
vector<vector<int>>bedist;
pair<int,int>mecho;
pair<int,int>dom;
bool good(int a,int b){
if(a<0||a>=n) return false;
if(b<0||b>=n) return false;
if(grid[a][b]=='G'||grid[a][b]=='M') return true;
else return false;
}
bool bear(int a,int b,int d){
return (d/s<bedist[a][b]);
}
bool ok(int eat){
vector<vector<int>>dist(n,vector<int>(n,mod));
dist[mecho.first][mecho.second]=eat*s;
queue<pair<int,int>>q;
q.push({mecho.first,mecho.second});
while(!q.empty()){
auto cur=q.front();q.pop();
for(int i=0;i<4;i++){
int a=cur.first+dir[i].first,b=cur.second+dir[i].second;
if(good(a,b)&&dist[a][b]>dist[a-dir[i].first][b-dir[i].second]+1&&bear(a,b,dist[a-dir[i].first][b-dir[i].second]+1)){
dist[a][b]=dist[a-dir[i].first][b-dir[i].second]+1;
q.push({a,b});
}
}
}bool f=false;
for(int i=0;i<4;i++){
int a=dom.first+dir[i].first,b=dom.second+dir[i].second;
if(good(a,b)&&dist[a][b]!=mod){
f=true;break;
}
}
return f;
}
void solve(){
cin>>n>>s;
vector<pair<int,int>>hives;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char c;cin>>c;
grid[i][j]=c;
if(c=='H'){
hives.pb({i,j});
}
if(c=='M') mecho={i,j};
if(c=='D') dom={i,j};
}
}
bedist=vector<vector<int>>(n,vector<int>(n,mod));
queue<pair<int,int>>q;
for(int i=0;i<(int)hives.size();i++){
q.push(hives[i]);
bedist[hives[i].first][hives[i].second]=0;
}
while(!q.empty()){
pair<int,int>cur=q.front();q.pop();
for(int i=0;i<4;i++){
if(good(cur.first+dir[i].first,cur.second+dir[i].second)&&bedist[cur.first][cur.second]+1<bedist[cur.first+dir[i].first][cur.second+dir[i].second]){
bedist[cur.first+dir[i].first][cur.second+dir[i].second]=bedist[cur.first][cur.second]+1;
q.push({cur.first+dir[i].first,cur.second+dir[i].second});
}
}
}
if(!ok(0)) {
cout<<-1<<endl;
return;
}
int l=0,r=n*n;
while(l<r){
int md=(l+r+1)/2;
if(ok(md)){
l=md;
}
else{
r=md-1;
}
}
cout<<l<<endl;
}
int main(){
int t=1;
while(t--) solve();
}
