#include <iostream>
#include <fstream>
using namespace std;
const int nmax=805;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
int d[nmax][nmax],a[nmax][nmax];
string s;
pair<int,int> q[nmax*nmax];
int p,u,n,m,i,j,li,ci,lf,cf,l1,l2,c1,c2,S,ans;
bool ok(int X,int Y)
{
return (X>=1&&Y>=1&&X<=n&&Y<=n);
}
void bfs()
{
p=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]==0)
q[++u]={i,j};
for(p=1;p<=u;p++)
{
li=q[p].first;ci=q[p].second;
for(i=0;i<4;i++)
{
lf=li+d1[i];cf=ci+d2[i];
if(ok(lf,cf)&&a[li][ci]+1<a[lf][cf])
{
a[lf][cf]=a[li][ci]+1;
q[++u]={lf,cf};
}
}
}
}
bool check(int val)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(d[i][j]!=-1)
d[i][j]=0;
d[l1][c1]=1;
q[p=u=1]={l1,c1};
for(p=1;p<=u;p++)
{
li=q[p].first;ci=q[p].second;
if(li==l2&&ci==c2) return 1;
if((d[li][ci]-1)/S+val>=a[li][ci]) continue;
for(i=0;i<4;i++)
{
lf=li+d1[i];cf=ci+d2[i];
if(ok(lf,cf)&&(!d[lf][cf]))
{
d[lf][cf]=d[li][ci]+1;
q[++u]={lf,cf};
}
}
}
return 0;
}
int main()
{
//freopen("data.in","r",stdin);
cin>>n>>S;
for(i=0;i<=n+1;i++)
for(j=0;j<=n+1;j++)
a[i][j]=(1<<30);
for(i=1;i<=n;i++)
{
cin>>s;
for(j=0;j<n;j++)
{
if(s[j]=='T') d[i][j+1]=a[i][j+1]=-1;
if(s[j]=='M') l1=i,c1=j+1;
if(s[j]=='D') l2=i,c2=j+1,a[i][j+1]=-1;
if(s[j]=='H') a[i][j+1]=0;
}
}
bfs();
for(int pu=20;pu>=0;pu--)
if(check(ans+(1<<pu)))
ans+=(1<<pu);
if(!check(0)) ans=-1;
cout<<ans;
return 0;
}
