#include<bits/stdc++.h>
using namespace std;
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define flip(x,i) (x^(1<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define sitingfake 1
#define orz 1
const int mod=1e9+7;
const long long linf=4557430888798830399;
const int inf=1061109567;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
const int maxn=1001;
int n,S;
int distH[maxn][maxn],distM[maxn][maxn];
char a[maxn][maxn];
ii st,fin;
int ans=-1;
void bfs1()
{
queue<ii>q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]=='H')
{
distH[i][j]=0;
q.push(ii(i,j));
}
else distH[i][j]=inf;
}
}
while(!q.empty())
{
int u=q.front().fi;
int v=q.front().se;
q.pop();
for(int z=0;z<4;z++)
{
int i=dx[z]+u;
int j=dy[z]+v;
if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]!='T'&&a[i][j]!='D')
{
if(distH[i][j]>distH[u][v]+1)
{
distH[i][j]=distH[u][v]+1;
q.push(ii(i,j));
}
}
}
}
}
bool check(int x)
{
queue<ii>q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
distM[i][j]=inf;
}
}
q.push(st);
distM[st.fi][st.se]=x*S;
while(!q.empty())
{
int u=q.front().fi;
int v=q.front().se;
q.pop();
for(int z=0;z<4;z++)
{
int i=dx[z]+u;
int j=dy[z]+v;
if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]!='T'&&a[i][j]!='D')
{
int val=distM[u][v]+1;
val/=S;
if(distM[i][j]>val&&val<distH[i][j])
{
distM[i][j]=distM[u][v]+1;
q.push(ii(i,j));
}
}
}
}
for(int z=0;z<4;z++)
{
int i=dx[z]+fin.fi;
int j=dy[z]+fin.se;
if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]!='T')
{
int val=distM[i][j]/S;
if(val<distH[i][j]) return 1;
}
}
return 0;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>S;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
if(a[i][j]=='M') st=ii(i,j);
else if(a[i][j]=='D')fin=ii(i,j);
}
}
bfs1();
int l=1,r=n+2;
while(l<=r)
{
int mid=(r+l)>>1;
if(check(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans;
//execute;
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT
*/
