#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>> q;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
cin >> grid[i][j];
if(grid[i][j] == 'M') {
bear_start = {i, j};
} else if(grid[i][j] == 'H') {
q.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(!q.empty()) {
int cy = q.front().first, cx = q.front().second;
q.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;
q.push({dy, dx});
}
}
function<void()> reset = [&]() {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
bear_dist[i][j] = INF;
}
}
};
function<bool(int)> possible = [&](int val) {
int sy = bear_start.first, sx = bear_start.second;
reset();
bear_dist[sy][sx] = 0;
if(bear_dist[sy][sx] + val >= bee_dist[sy][sx]) return false;
queue<pair<int, int>> qb;
bool pos = false;
qb.push({sy, sx});
while(!qb.empty()) {
int cy = qb.front().first, cx = qb.front().second;
qb.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) &&
bear_dist[dy][dx] == INF &&
((bear_dist[cy][cx] + 1) / s + val) < bee_dist[dy][dx]
) {
bear_dist[dy][dx] = bear_dist[cy][cx] + 1;
qb.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";
}
