#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> v;
ll N, S, ini, fin;
bool solve(ll T, deque<ll> bfs, vector<bool> vis, vector<char> ori){
bfs.push_front(-1);
vis[ini] = true;
vector<ll> q1, q2;
q1.push_back(ini);
while(bfs.size() != 0){
ll x = bfs.front();
bfs.pop_front();
if(x == -1 and T != 0){
T--;
bfs.push_back(-1);
continue;
}
if(x == -1){
for(ll i=0;i<S;i++){
while(q1.size() != 0){
ll y = q1.back();
for(ll z : v[y]){
if(z == fin){return true;}
if(vis[z]){continue;}
vis[z] = true;
ori[z] = 'M';
//cout<<"Casilla "<<z/N<<" "<<z%N<<" pasa a tener origen M"<<endl;
q2.push_back(z);
}
q1.pop_back();
}
swap(q1, q2);
}
if(q1.size() != 0){bfs.push_back(-1);}
continue;
}
for(ll y : v[x]){
if(ori[y] == 'D'){continue;}
if(ori[y] == 'M'){
ori[y] = 'H';
//cout<<"Casilla "<<y/N<<" "<<y%N<<" pasa a tener origen H"<<endl;
}
if(vis[y]){continue;}
vis[y] = true;
ori[y] = 'H';
//cout<<"Casilla "<<y/N<<" "<<y%N<<" pasa a tener origen H"<<endl;
bfs.push_back(y);
}
}
return false;
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin>>N>>S;
v.resize(N*N);
vector<char> c(N*N);
deque<ll> d;
vector<bool> fij(N*N, false);
for(ll i=0;i<N;i++){
for(ll j=0;j<N;j++){
cin>>c[N*i+j];
if(c[N*i+j] == 'H'){
d.push_back(N*i+j);
fij[N*i+j] = true;
}
if(c[N*i+j] == 'M'){ini = N*i+j;}
if(c[N*i+j] == 'D'){
fin = N*i+j;
}
}
}
for(ll i=0;i<N;i++){
for(ll j=0;j<N;j++){
if(i > 0 and c[N*(i-1)+j] != 'T'){
v[N*i+j].push_back(N*(i-1)+j);
}
if(i < N-1 and c[N*(i+1)+j] != 'T'){
v[N*i+j].push_back(N*(i+1)+j);
}
if(j > 0 and c[N*i+(j-1)] != 'T'){
v[N*i+j].push_back(N*i+(j-1));
}
if(j < N-1 and c[N*i+(j+1)] != 'T'){
v[N*i+j].push_back(N*i+(j+1));
}
}
}
/*if(solve(1, d, fij, c)){cout<<"meow";}
else{cout<<"wof";}*/
if(!(solve(0, d, fij, c))){cout<<-1; return 0;}
ll l = 0;
ll r = N*N;
while(r != l+1){
ll m = (l+r)/2;
if(solve(m, d, fij, c)){l = m;}
else{r = m;}
//cout<<l<<" "<<r<<endl;
}
cout<<l;
}
