#include<bits/stdc++.h>
using namespace std;
int dx[] = {0,1,0,-1} , dy[] = {1,0,-1,0} ,x ,y , st ,N , si , sj , fi , fj;
const int n=801;
char s[n][n];
vector<vector<int>>timebee(n , vector<int>(n,INT_MAX));
vector<vector<int>>timebear(n , vector<int>(n,INT_MAX));
vector<vector<int>>visbee(n , vector<int>(n,0));
queue<pair<pair<int,int>,int>>qbear,qbee;
int check(int m)
{
//cout << m << endl;
if(m>timebee[fi][fj])return 0;
while(!qbear.empty())qbear.pop();
for(int i=0 ; i<N ; i++)for(int j=0 ; j<N ; j++)timebear[i][j]=INT_MAX;
vector<vector<int>>visbear(N , vector<int>(N,0));
qbear.push({{si,sj},0});
timebear[si][sj] = m;
visbear[si][sj] = 1;
while(!qbear.empty())
{
int r = qbear.front().first.first , c = qbear.front().first.second , time = qbear.front().second;
//cout << r << " " << c << " " << time << endl;
qbear.pop();
for(int i=0 ; i<4 ; i++)
{
int nr = r+dx[i];
int nc = c+dy[i];
if(nr<0 or nr>=N or nc<0 or nc>=N or s[nr][nc]=='T' or visbear[nr][nc]==1)continue;
if((time+1)%st==0)timebear[nr][nc]=timebear[r][c]+1;
else timebear[nr][nc]=timebear[r][c];
if(timebee[nr][nc]<=timebear[nr][nc])continue;
visbear[nr][nc]=1;
qbear.push({{nr,nc},time+1});
}
}
/*for(int i=0 ; i<N ; i++)
{
for(int j=0 ; j<N ; j++)
{
if(timebear[i][j]!=INT_MAX)cout << timebear[i][j];
else cout << 0;
}
cout << endl;
}
cout << endl;
for(int i=0 ; i<N ; i++)
{
for(int j=0 ; j<N ; j++)
{
if(timebee[i][j]!=INT_MAX)cout << timebee[i][j];
else cout << 0;
}
cout << endl;
}*/
if(timebear[fi][fj]!=INT_MAX)return 1;
else return 0;
}
int main()
{
cin >> N >> st;
for(int i=0 ; i<N ; i++)
{
for(int j=0 ; j<N ; j++)
{
cin >> s[i][j];
if(s[i][j]=='M')
{
si=i;
sj=j;
}
if(s[i][j]=='D')
{
fi=i;
fj=j;
}
if(s[i][j]=='H')
{
qbee.push({{i,j},0});
visbee[i][j] = 1;
timebee[i][j]=0;
}
}
}
while(!qbee.empty())
{
int r = qbee.front().first.first , c = qbee.front().first.second , time = qbee.front().second;
qbee.pop();
for(int i=0 ; i<4 ; i++)
{
int nr = r+dx[i];
int nc = c+dy[i];
if(nr<0 or nr>=N or nc<0 or nc>=N or s[nr][nc]=='D' or s[nr][nc]=='T' or visbee[nr][nc])continue;
visbee[nr][nc]=1;
timebee[nr][nc] = time+1;
qbee.push({{nr,nc},timebee[nr][nc]});
}
}
int l=0 ,r=N*N , m ,ans=-1;
while(l<=r)
{
m=l+(r-l)/2;
if(check(m))ans=m , l=m+1;
else r=m-1;
}
//check(2);
cout << ans ;
}
