#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int N=805;
const int oo=1e9+1;
const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int n,mx_steps,start_x,start_y,l,r,mid,res;
pii new_dist;
int d[N][N];
pii dTwo[N][N];
char s[N][N];
queue <pii> q;
void pre_bfs()
{
while (!q.empty()) q.pop();
int u,v,x,y;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (s[i][j]=='H')
{
d[i][j]=0;
q.push(make_pair(i,j));
}
else d[i][j]=oo+1;
while (!q.empty())
{
u=q.front().X;
v=q.front().Y;
q.pop();
for (int i=0;i<4;i++)
{
x=u+dx[i];
y=v+dy[i];
if (x>0 and x<=n and y>0 and y<=n and (s[x][y]=='G' or s[x][y]=='M') and d[x][y]>d[u][v]+1)
{
d[x][y]=d[u][v]+1;
q.push(make_pair(x,y));
}
}
}
}
bool check(int u,int v,int mid)
{
while (!q.empty()) q.pop();
int x,y;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
dTwo[i][j]=make_pair(oo,oo);
dTwo[u][v]=make_pair(mid,0);
q.push(make_pair(u,v));
while (!q.empty())
{
u=q.front().X;
v=q.front().Y;
q.pop();
new_dist=make_pair(dTwo[u][v].X,dTwo[u][v].Y+1);
if (new_dist.Y==mx_steps)
{
new_dist.X++;
new_dist.Y=0;
}
for (int i=0;i<4;i++)
{
x=u+dx[i];
y=v+dy[i];
if (x>0 and x<=n and y>0 and y<=n and (s[x][y]!='T' and s[x][y]!='H') and d[x][y]>new_dist.X and dTwo[x][y]>new_dist)
{
if (s[x][y]=='D') return true;
dTwo[x][y]=new_dist;
q.push(make_pair(x,y));
}
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> mx_steps;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
cin >> s[i][j];
if (s[i][j]=='M')
{
start_x=i;
start_y=j;
}
}
pre_bfs();
res=-1;
l=0;
r=d[start_x][start_y]-1;
while (l<=r)
{
mid=(l+r)/2;
if (check(start_x,start_y,mid))
{
res=mid;
l=mid+1;
}
else r=mid-1;
}
cout << res;
}
