#include <bits/stdc++.h>
#define MAX 850
std::string mapa[MAX];
typedef std::pair<int,int> pii;
bool proibido[MAX][MAX]={},nobees[MAX][MAX]={};
int N,K;
typedef std::pair<int,pii> pip;
std::vector<pii> hon;
void avancar(void) {
std::vector<pii> honfut;
for(auto&x:hon) {
#define PUSH(A,B) if(A>=0&&B>=0&&A<N&&B<N&&!proibido[A][B]&&!nobees[A][B]){proibido[A][B]=true;honfut.push_back({A,B});}
PUSH(x.first+1,x.second);
PUSH(x.first-1,x.second);
PUSH(x.first,x.second+1);
PUSH(x.first,x.second-1);
}
hon=honfut;
}
bool vis[MAX][MAX]={};
bool testar(int x,int s) {
hon.clear();
memset(&proibido[0][0],0,sizeof(proibido));
memset(&nobees[0][0],0,sizeof(nobees));
memset(&vis[0][0],0,sizeof(vis));
pii inicio,fim;
for(int i=0;i!=N;++i){
for(int j=0;j!=N;++j){
if(mapa[i][j]=='H'){
proibido[i][j]=true;
hon.push_back({i,j});
}else if(mapa[i][j]=='M') {
inicio={i,j};
}else if(mapa[i][j]=='D') {
nobees[i][j]=true;
fim={i,j};
}else if(mapa[i][j]=='T'){
nobees[i][j]=true;
proibido[i][j]=true;
}
}
}
for(int i=0;i!=x;++i)avancar();
std::queue<pip> queue;
queue.push({0,inicio});
int laste=0;
while(queue.size()) {
auto _ = queue.front();
queue.pop();
int mov = _.first/s;
if(mov>laste){
laste=mov;
avancar();
}
if(vis[_.second.first][_.second.second]||proibido[_.second.first][_.second.second])continue;
vis[_.second.first][_.second.second]=true;
if(_.second==fim)return true;
#define QPUSH(A,B) if(A>=0&&B>=0&&A<N&&B<N)queue.push({_.first+1,{A,B}});
QPUSH(_.second.first+1,_.second.second);
QPUSH(_.second.first-1,_.second.second);
QPUSH(_.second.first,_.second.second+1);
QPUSH(_.second.first,_.second.second-1);
}
return false;
}
int main()
{
std::cin>>N>>K;
for(int i=0;i!=N;++i)std::cin>>mapa[i];
if(!testar(0,K)) {
std::cout<<-1<<"\n";
return 0;
}
int l=0,r=N*N;
while(l<r) {
int m = (l+r)/2 + ((l+r)&1);
if(testar(m,K)) {
l=m;
}else r=m-1;
}
std::cout<<l<<"\n";
}
