#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b){
if(b == 0) return a;
return gcd(b, a % b);
}
long long _gcd(long long n1,long long n2)
{ while (n2!=0){
long long temp=n1;
n1=n2;
n2=temp%n1;
}
return n1;
}
long long _lcm(long long n1,long long n2){
return (n1/ _gcd(n1,n2))*n2;
}
bool prime(long long n){
if(n==2)return true;
if(n<2||n%2==0)return false;
int d= sqrtl(n);
for(int i=3;i<= d;i+=2)
if(n%i==0)return false;
return true;
}
string to_binary(long long x){
string s="";
while(x){
int d=x%2;
char c=d+'0';
s+=c;
x/=2;
}
return s;
}
long long to_dec(string s){
long long su=0;
int d=0;
for(long long i=0;i<(s.size());i++){
if(s[i]=='0')continue;
long long q= round(pow(2LL,i));
su+=q;
}
return su;
}
bool com(pair<long long ,long long >&x,pair<long long ,long long >&y){
if(x.first!=y.first)return x.first>y.first;
return x.second<y.second;
}
void Nozarashi(){
long long n,k;
cin>>n>>k;
vector<string>grid;
for(int i=0;i<n;i++){
string s;
cin>>s;
grid.push_back(s);
}
long long s1,s2;
for(int i=0;i<int(grid.size());i++){
for(int j=0;j<int(grid[i].size());j++){
if(grid[i][j]=='M'){
s1=i;
s2=j;
}
}
}
function<bool(int ,int,int,int)>in_range=[&](int i,int j,int n,int m){
if(i>=0&&i<n&&j>=0&&j<m)return true;
return false;
};
function<bool(long long ) >bfs=[&](long long mi){
long long visted[n+3][n+3];
memset(visted,0,sizeof(visted));
queue<pair<int,int> >qe;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='H'){qe.push({i,j});
visted[i][j]=true;}
}
}
int level=0;
while(!qe.empty()){
if(level==mi)break;
long long sz=qe.size();
for(int d=0;d<sz;d++){
long long i=qe.front().first;
long long j=qe.front().second;
qe.pop();
for(int I=-1;I<=1;I++){
for(int J=-1;J<=1;J++){
if(abs(I)==abs(J))continue;
long long t1=i+I;
long long t2=j+J;
if(!in_range(t1,t2,n,n))continue;
if(visted[t1][t2])continue;
if(grid[t1][t2]=='M'){
return false;
}
if(grid[t1][t2]=='D')continue;
if(grid[t1][t2]=='T')continue;
qe.push({t1,t2});
visted[t1][t2]=true;
}
}
}
level++;
}
level=0;
queue<pair<int,int > >qem;
qem.push({s1,s2});
visted[s1][s2]=true;
while(!qem.empty()||!qe.empty()){
long long sz=qe.size();
if((level+1)%k==0){
for(int d=0;d<sz;d++){
long long i=qe.front().first;
long long j=qe.front().second;
qe.pop();
for(int I=-1;I<=1;I++){
for(int J=-1;J<=1;J++){
if(abs(I)==abs(J))continue;
long long t1=i+I;
long long t2=j+J;
if(!in_range(t1,t2,n,n))continue;
if(visted[t1][t2])continue;
if(grid[t1][t2]=='T')continue;
qe.push({t1,t2});
visted[t1][t2]=true;
}
}
}
sz=qem.size();
for(int d=0;d<sz;d++){
long long i=qem.front().first;
long long j=qem.front().second;
qem.pop();
for(int I=-1;I<=1;I++){
for(int J=-1;J<=1;J++){
if(abs(I)==abs(J))continue;
long long t1=i+I;
long long t2=j+J;
if(!in_range(t1,t2,n,n))continue;
if(visted[t1][t2])continue;
if(grid[t1][t2]=='D')return true;
if(grid[t1][t2]=='T')continue;
qem.push({t1,t2});
visted[t1][t2]=true;
}
}
}
}
else {
sz=qem.size();
for(int d=0;d<sz;d++){
long long i=qem.front().first;
long long j=qem.front().second;
qem.pop();
for(int I=-1;I<=1;I++){
for(int J=-1;J<=1;J++){
if(abs(I)==abs(J))continue;
long long t1=i+I;
long long t2=j+J;
if(!in_range(t1,t2,n,n))continue;
if(visted[t1][t2])continue;
if(grid[t1][t2]=='T')continue;
if(grid[t1][t2]=='D')return true;
qem.push({t1,t2});
visted[t1][t2]=true;
}
}
}
}
level++;
}
return false;
};
long long l=0,r=1e9,ans=-1;
while(l<=r){
long long mid=l+(r-l)/2;
if(bfs(mid)){
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//// freopen("lasers.in", "r", stdin);
// freopen("lasers.out", "w", stdout);
int t=1;
while (t--){
Nozarashi();
}
return 0;
}
