#include <bits/stdc++.h>
using namespace std;
const int N=805;
int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};
int n,s;
char v[N][N];
int mecho[N][N], bees[N][N];
bool check(int i, int j){
return 0<=i && i<n && 0<=j && j<n;
}
pair<int, int>start,finish;
bool verif(int x){
memset(mecho, (1<<6)-1, sizeof(mecho));
queue<pair<int, int>> q;
q.push(start);
mecho[start.first][start.second]=x*s;
if (x>=bees[start.first][start.second]){
return false;
}
while (!q.empty()){
auto z=q.front();q.pop();
int i=z.first;
int j=z.second;
int d=mecho[i][j]+1;
int t=d/s+(d%s==0?0:1);
for (int k=0;k<4;k++){
int newi=i+di[k];
int newj=j+dj[k];
if (check(newi, newj) && (v[newi][newj]=='G') && mecho[newi][newj]>d){
if (d%s==0 && bees[newi][newj]==t){
continue;//will be caught on the next move cause he is out of moves
}
else{
t++;
}
if (bees[newi][newj]>=t){
mecho[newi][newj]=d;
q.push({newi, newj});
}
}
}
}
/*if (x<3){
cout<<x<<endl;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (mecho[i][j]>1e9){
cout<<-1;
}
else{
if (mecho[i][j]>9){
cout<<mecho[i][j];
}
else{
cout<<' '<<mecho[i][j];
}
}
cout<<' ';
}
cout<<'\n';
}
}*/
int i=finish.first;
int j=finish.second;
for (int k=0;k<4;k++){
int newi=i+di[k];
int newj=j+dj[k];
if (check(newi, newj) && mecho[newi][newj]<1e9){
int d=mecho[newi][newj];
int t=d/s;
if (d%s==0 && bees[newi][newj]==t){//is the last move on that second and the bees catch him
continue;
}
if (bees[newi][newj]>=t){//he still has at least one move in that second and can reach the home safely
mecho[i][j]=d+1;
}
}
}
if (mecho[i][j]<1e9){
return true;
}
else{
return false;
}
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("input.in", "r", stdin);
#endif // ONLINE_JUDGE
memset(bees, (1<<6)-1, sizeof(bees));
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>s;
queue<pair<int, int>> q;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
cin>>v[i][j];
if (v[i][j]=='M'){
start={i,j};
v[i][j]='G';
}
else if (v[i][j]=='H'){
bees[i][j]=0;
q.push({i,j});
}
else if (v[i][j]=='D'){
finish={i,j};
}
}
}
while (!q.empty()){
auto z=q.front();q.pop();
int i=z.first;
int j=z.second;
int d=bees[i][j];
for (int k=0;k<4;k++){
int newi=i+di[k];
int newj=j+dj[k];
if (check(newi, newj) && v[newi][newj]=='G' && bees[newi][newj]>d+1){
bees[newi][newj]=d+1;
q.push({newi, newj});
}
}
}
/*for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (bees[i][j]>1e9){
cout<<-1;
}
else{
if (bees[i][j]>9){
cout<<bees[i][j];
}
else{
cout<<' '<<bees[i][j];
}
}
cout<<' ';
}
cout<<'\n';
}*/
int left=0, right=n*n;
int ans=-1;
while (left<=right){
int mid=(left+right)/2;
if (verif(mid)){
ans=mid;
left=mid+1;
}
else{
right=mid-1;
}
}
cout<<ans;
}
