#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int bulan=300000;
const int dx[]={0, 0, -1, 1};
const int dy[]={-1, 1, 0, 0};
int n, s, ok;
int viz[805][805], blocked[805][805], xs, ys, ye, xe, viz2[805][805];
char mat[805][805];
vector <pair <int, int>> initial, trees;
queue <vector <int>> coadab;
queue <vector <int>> coada;
bool ismat (int i, int j)
{
return i>=1 && j>=1 && i<=n && j<=n;
}
void moveBees (int time)
{
while (!coadab.empty())
{
int x=coadab.front()[0];
int y=coadab.front()[1];
int val=coadab.front()[2];
if (val>time)
break;
coadab.pop();
blocked[x][y]=1;
for (int i=0;i<=3;i++)
{
int inou=dx[i]+x;
int jnou=dy[i]+y;
if (ismat (inou, jnou) && !viz[inou][jnou] && (mat[inou][jnou]=='G' || mat[inou][jnou]=='M'))
{
viz[inou][jnou]=1;
coadab.push ({inou, jnou, val+1});
}
}
}
}
void moveBear (int time)
{
while (!coada.empty())
{
int x=coada.front()[0];
int y=coada.front()[1];
int step=coada.front()[2];
if (step>s*time)
break;
coada.pop();
if (blocked[x][y])
continue;
if (x==xe && y==ye)
ok=1;
for (int i=0;i<=3;i++)
{
int inou=dx[i]+x;
int jnou=dy[i]+y;
if (ismat (inou, jnou) && !viz2[inou][jnou] && !blocked[inou][jnou] && (mat[inou][jnou]=='G' || mat[inou][jnou]=='D'))
{
viz2[inou][jnou]=1;
coada.push ({inou, jnou, step+1});
}
}
}
}
bool check (int val)
{
ok=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
viz[i][j]=0;
viz2[i][j]=0;
blocked[i][j]=0;
}
}
coada.push ({xs, ys, 1});
viz2[xs][ys]=1;
for (auto tree : trees)
{
blocked[tree.first][tree.second]=1;
viz[tree.first][tree.second]=1;
}
for (auto poz : initial)
{
viz[poz.first][poz.second]=1;
coadab.push ({poz.first, poz.second, 0});
}
moveBees (0);
int mx=0;
for (int crt_time=1;;crt_time++)
{
mx=crt_time;
if (coada.empty())
break;
if (crt_time>val) moveBear (crt_time-val);
if (ok)
{
break;
}
moveBees (crt_time);
}
while (!coada.empty())
coada.pop();
while (!coadab.empty())
coadab.pop();
return ok;
}
int main ()
{
cin >> n >> s;
for (int i=1;i<=n;i++)
{
string s;
cin >> s;
for (int j=1;j<=n;j++)
{
mat[i][j]=s[j-1];
if (mat[i][j]=='T')
{
trees.push_back ({i, j});
}
if (mat[i][j]=='H')
{
initial.push_back ({i, j});
}
if (mat[i][j]=='M')
{
xs=i;
ys=j;
}
if (mat[i][j]=='D')
{
ye=j;
xe=i;
}
}
}
int st=0, dr=bulan+1, poz=-1;
while (st<=dr)
{
int mij = (st+dr) >> 1;
if (check (mij))
{
st=mij+1;
poz=mij;
}
else dr=mij-1;
}
cout << poz;
return 0;
}
