#include <bits/stdc++.h>
using namespace std;
char grid[800][800];
int bee_dist[800][800];
int bear_dist[800][800];
bool vis_dfs[800][800];
const int INF = 2000000005;
vector<pair<int,int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
int main(){
pair<int,int> bear_start;
pair<int,int> end;
int n,s; cin >> n >> s;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
bee_dist[i][j] = bear_dist[i][j] = INF;
}
}
queue<pair<int,int>> q1, q2;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> grid[i][j];
if(grid[i][j]=='M'){
q1.push({i,j});
bear_dist[i][j] = 0;
bear_start = {i,j};
} else if(grid[i][j]=='H'){
q2.push({i,j});
bee_dist[i][j] = 0;
} else if(grid[i][j]=='D'){
end = {i,j};
}
}
}
auto valid = [&](int y,int x) -> bool {
return (y>=0 && y<n && x>=0 && x<n && grid[y][x]!='T');
};
while(!q1.empty()){
int cy = q1.front().first, cx = q1.front().second;
q1.pop();
for(auto d: dirs){
int ny = cy+d.first, nx = cx+d.second;
if(!valid(ny,nx) || bear_dist[ny][nx]!=INF) continue;
bear_dist[ny][nx] = bear_dist[cy][cx] + 1;
q1.push({ny,nx});
}
}
while(!q2.empty()){
int cy = q2.front().first, cx = q2.front().second;
q2.pop();
for(auto d: dirs){
int ny = cy+d.first, nx = cx+d.second;
if(!valid(ny,nx) || bee_dist[ny][nx]!=INF || grid[ny][nx]=='D') continue;
bee_dist[ny][nx] = bee_dist[cy][cx] + 1;
q2.push({ny,nx});
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(bear_dist[i][j]==INF) continue;
bear_dist[i][j] = ceil(bear_dist[i][j] / (double)s);
}
}
function<void(int,int,int)> repl = [&](int y,int x,int cr){
if(cr > s || !valid(y,x)) return;
if(vis_dfs[y][x]) return;
vis_dfs[y][x] = true;
bear_dist[y][x] = 0;
for(auto d: dirs){
int ny = y+d.first, nx = x+d.second;
repl(ny,nx,cr+1);
}
};
repl(end.first,end.second,0);
auto possible = [&](int w) -> bool {
int sy = bear_start.first, sx = bear_start.second;
if(bear_dist[sy][sx] + w >= bee_dist[sy][sx]) return false;
vector<vector<bool>> vis(n, vector<bool>(n, false));
queue<pair<int,int>> q;
q.push({sy,sx});
vis[sy][sx] = true;
while(!q.empty()){
int cy = q.front().first, cx = q.front().second;
q.pop();
if(grid[cy][cx]=='D') return true;
for(auto d: dirs){
int ny = cy+d.first, nx = cx+d.second;
if(valid(ny,nx) && !vis[ny][nx] && bear_dist[ny][nx] + w < bee_dist[ny][nx]){
vis[ny][nx] = true;
q.push({ny,nx});
}
}
}
return false;
};
int lo = 0, hi = 1000000, ans = -1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(possible(mid)){
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans << "\n";
return 0;
}
