#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int nx = 805;
int n, s, l=0, r=nx*nx, md, ans=0;
string grid[nx];
pair<int, int> bear, dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
set<pair<int, int>> bee;
bool check(int sz, int steps){
vector<vector<bool>> b(sz, vector<bool>(sz, false)), br(sz, vector<bool>(sz, false));
queue<pair<int, pair<int, int>>> bq, brq;
for(auto [y, x] : bee) bq.push({0, {y, x}});
brq.push({0, {bear.ff, bear.ss}});
int bt = md, brt = steps;
while(!brq.empty()){
// cout << "!EMPTY\n";
while(!bq.empty() && bq.front().ff<bt){
// cout << "LOOP1\n";
int mins = bq.front().ff;
pair<int, int> pos = bq.front().ss;
bq.pop();
if(b[pos.ff][pos.ss]) continue;
b[pos.ff][pos.ss] = true;
for(int i=0; i<4; i++){
int ny = pos.ff+dir[i].ff, nx = pos.ss+dir[i].ss;
if(ny>=0 && ny<n && nx>=0 && nx<n && grid[ny][nx]!='T' && !b[ny][nx] && grid[ny][nx]!='D'){
bq.push({mins+1, {ny, nx}});
}
}
} bt++;
while(!brq.empty() && brq.front().ff<brt){
// cout << "LOOP2\n";
int mins = brq.front().ff;
pair<int, int> pos = brq.front().ss;
brq.pop();
if(br[pos.ff][pos.ss] || b[pos.ff][pos.ss]) continue;
br[pos.ff][pos.ss] = true;
for(int i=0; i<4; i++){
int ny = pos.ff+dir[i].ff, nx = pos.ss+dir[i].ss;
if(ny>=0 && ny<n && nx>=0 && nx<n && grid[ny][nx]!='T' && !br[ny][nx]){
if(grid[ny][nx]=='D') return true;
brq.push({mins+1, {ny, nx}});
}
}
} brt+=steps;
}
return false;
}
int main(){
// cin.tie(NULL)->sync_with_stdio(false);
bool cando = false;
cin >> n >> s;
for(int i=0; i<n; i++){
cin >> grid[i];
for(int j=0; j<n; j++){
if(grid[i][j]=='H') bee.insert({i, j});
else if(grid[i][j]=='M') bear = {i, j};
}
}
while(l<=r){
md = l+(r-l)/2;
if(check(n, s)){
cando = true;
ans = md;
l = md+1;
} else r = md-1;
}
if(cando) cout << ans-1;
else cout << -1;
return 0;
}
