#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
const int N = 1010;
char a[N][N];
int n,m;
const int xp[]={1,-1,0,0};
const int yp[]={0,0,1,-1};
int dis1[N][N],dis2[N][N];
bool check(int limit) {
int i,j,k; queue<pii> q; pii u;
int nx,ny,x,y;
memset(dis1,0x3f,sizeof(dis1));
memset(dis2,0x3f,sizeof(dis2));
for(i=1;i<=n;i++) for(j=1;j<=n;j++) {
if(a[i][j]=='H') {
q.push(mp(i,j));
dis1[i][j]=0;
}
}
while(!q.empty()) {
u=q.front(); q.pop(); tie(x,y)=u;
for(k=0;k<4;k++) {
nx=x+xp[k],ny=y+yp[k];
if(1<=nx&&nx<=n&&1<=ny&&ny<=n&&dis1[nx][ny]>dis1[x][y]+1&&(a[nx][ny]=='G'||a[nx][ny]=='M')) {
dis1[nx][ny]=dis1[x][y]+1;
q.push(mp(nx,ny));
}
}
}
for(i=1;i<=n;i++) for(j=1;j<=n;j++) {
if(a[i][j]=='M') {
q.push(mp(i,j));
dis2[i][j]=0;
if(limit>=dis1[i][j]) return 0;
}
}
while(!q.empty()) {
u=q.front(); q.pop(); tie(x,y)=u;
for(k=0;k<4;k++) {
nx=x+xp[k],ny=y+yp[k];
if(1<=nx&&nx<=n&&1<=ny&&ny<=n&&dis2[nx][ny]>dis2[x][y]+1&&a[nx][ny]!='T') {
if((dis2[x][y]+1)/m+limit<dis1[nx][ny]) {
dis2[nx][ny]=dis2[x][y]+1;
q.push(mp(nx,ny));
}
}
}
}
for(i=1;i<=n;i++) for(j=1;j<=n;j++) {
if(a[i][j]=='D') {
if(dis2[i][j]!=0x3f3f3f3f) {
return 1;
}
}
}
return 0;
}
int main() {
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++) cin>>(a[i]+1);
int l=0,r=1000005,mid;
while(l<=r) {
mid=(l+r)/2;
if(check(mid)) l=mid+1;
else r=mid-1;
} cout<<r<<endl;
return 0;
}
