#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF=1e9+7;
const int N=800;
struct Pos
{
int x,y;
Pos(int _x=0,int _y=0) : x(_x), y(_y) {};
bool operator==(const Pos &oth)
{
return (x==oth.x && y==oth.y);
}
vector<Pos> edges()
{
vector<Pos> tmp;
tmp.reserve(4);
for(auto dd:{make_pair(0,-1),make_pair(0,1),make_pair(-1,0),make_pair(1,0)})
tmp.push_back({x+dd.fi,y+dd.se});
return tmp;
}
};
bool fr[N+10][N+10];
queue<Pos> qq;
int bt[N+10][N+10];
pair<int,int> d[N+10][N+10];
bool ok(Pos start,Pos finish,int s,int time,int n)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
d[i][j]={INF,INF};
}
d[start.x][start.y]={time,0};
qq.push(start);
while(!qq.empty())
{
auto x=qq.front();
qq.pop();
vector<Pos> e=x.edges();
pair<int,int> tn=(d[x.x][x.y].se+1>=s ? make_pair(d[x.x][x.y].fi+1,0):
make_pair(d[x.x][x.y].fi,d[x.x][x.y].se+1));
for(auto v:e)
{
if((fr[v.x][v.y] || v==finish) && d[v.x][v.y].se==INF && bt[v.x][v.y]>tn.fi)
{
d[v.x][v.y]=tn;
qq.push(v);
}
}
}
return (d[finish.x][finish.y].se!=INF);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,s;
Pos start,finish;
cin>>n>>s;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
bt[i][j]=INF;
char c;
cin>>c;
if(c=='T')
{
fr[i][j]=false;
}
else if(c=='G')
{
fr[i][j]=true;
}
else if(c=='M')
{
fr[i][j]=true;
start=Pos(i,j);
}
else if(c=='D')
{
fr[i][j]=false;
finish=Pos(i,j);
}
else if(c=='H')
{
fr[i][j]=false;
qq.push(Pos(i,j));
bt[i][j]=0;
}
}
}
while(!qq.empty())
{
Pos a=qq.front();
qq.pop();
vector<Pos> e=a.edges();
for(auto v:e)
{
if(fr[v.x][v.y] && bt[v.x][v.y]==INF)
{
bt[v.x][v.y]=bt[a.x][a.y]+1;
qq.push(v);
}
}
}
//for(int i=1;i<=n;i++)
//{
// for(int j=1;j<=n;j++)
// cerr<<bt[i][j]<<" ";
// cerr<<"\n";
//}
if(!ok(start,finish,s,0,n))
{
cout<<"-1\n";
return 0;
}
int bg=0,en=bt[start.x][start.y]-1;
while(bg<en)
{
int mid=(bg+en+1)/2;
if(ok(start,finish,s,mid,n))
bg=mid;
else
en=mid-1;
}
cout<<bg<<"\n";
return 0;
}
