#include <bits/stdc++.h>
using namespace std;
char grid[800][800];
int bee_dist[800][800];
int bear_dist[800][800];
bool visited[800][800];
const int INF = 2e9+5;
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int main() {
pair<int, int> bear_start;
pair<int, int> end;
for(int i = 0; i < 800; ++i) {
for(int j = 0; j < 800; ++j) {
bee_dist[i][j] = bear_dist[i][j] = INF;
}
}
int n, s; cin >> n >> s;
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};
}
}
}
function<bool(int, int)> valid = [&](int y, int x) {
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 dir : dirs) {
int dy = cy + dir.first;
int dx = cx + dir.second;
if(!valid(dy, dx) || bear_dist[dy][dx] != INF) continue;
bear_dist[dy][dx] = bear_dist[cy][cx] + 1;
q1.push({dy, dx});
}
}
while(!q2.empty()) {
int cy = q2.front().first, cx = q2.front().second;
q2.pop();
for(auto dir : dirs) {
int dy = cy + dir.first;
int dx = cx + dir.second;
if(!valid(dy, dx) || bee_dist[dy][dx] != INF || grid[dy][dx] == 'D') continue;
bee_dist[dy][dx] = bee_dist[cy][cx] + 1;
q2.push({dy, dx});
}
}
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 (visited[y][x]) return;
if(cr > s) return;
visited[y][x] = true;
bear_dist[y][x] = 0;
for(auto dir : dirs) {
int dy = y + dir.first;
int dx = x + dir.second;
if(!valid(dy, dx)) continue;
repl(dy, dx, cr + 1);
}
};
repl(end.first, end.second, 0);
function<bool(int)> possible = [&](int val) {
int sy = bear_start.first, sx = bear_start.second;
if(bear_dist[sy][sx] + val >= bee_dist[sy][sx]) return false;
vector<vector<bool>> vis(n, vector<bool>(n));
queue<pair<int, int>> q3;
bool pos = false;
q3.push({sy, sx});
vis[sy][sx] = true;
while(!q3.empty()) {
int cy = q3.front().first, cx = q3.front().second;
q3.pop();
if(grid[cy][cx] == 'D') {
pos = true;
break;
}
for(auto dir : dirs) {
int dy = cy + dir.first;
int dx = cx + dir.second;
if(valid(dy, dx) && !vis[dy][dx] && bear_dist[dy][dx] + val < bee_dist[dy][dx]) {
vis[dy][dx] = true;
q3.push({dy, dx});
}
}
}
return pos;
};
int l = 0, r = 1'000'000, best = -1;
while(l < r) {
int mid = l + (r - l) / 2;
if(possible(mid)) {
best = mid;
l = mid + 1;
} else {
r = mid;
}
}
cout << best << "\n";
}
