#include <bits/stdc++.h>
using namespace std;
const int N = 805;
int n, s;
char grid[N][N];
int bee_time[N][N], mecho_time[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
pair<int, int> start, home;
vector<pair<int, int>> hives;
bool in_bounds(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
void bfs_bees() {
queue<pair<int, int>> q;
for (auto [x, y] : hives) {
bee_time[x][y] = 0;
q.push({x, y});
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (!in_bounds(nx, ny)) continue;
if (grid[nx][ny] == 'T' || grid[nx][ny] == 'D') continue; // Bees can't enter trees or home
if (bee_time[nx][ny] > bee_time[x][y] + s) {
bee_time[nx][ny] = bee_time[x][y] + s;
q.push({nx, ny});
}
}
}
}
bool can_escape(int wait_time) {
for (int i = 0; i < n; i++)
fill(mecho_time[i], mecho_time[i] + n, INT_MAX);
queue<pair<int, int>> q;
mecho_time[start.first][start.second] = wait_time;
q.push(start);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (!in_bounds(nx, ny)) continue;
if (grid[nx][ny] == 'T') continue;
int arrive = mecho_time[x][y] + 1;
if (arrive >= bee_time[nx][ny]) continue; // bees arrive before or same second
if (mecho_time[nx][ny] > arrive) {
mecho_time[nx][ny] = arrive;
if (grid[nx][ny] == 'D') return true;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
for (int i = 0; i < n; i++)
cin >> grid[i];
for (int i = 0; i < n; i++)
fill(bee_time[i], bee_time[i] + n, INT_MAX);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'M') start = {i, j};
if (grid[i][j] == 'D') home = {i, j};
if (grid[i][j] == 'H') hives.emplace_back(i, j);
}
}
bfs_bees();
int l = 0, r = (n * n + s - 1) / s + 10; // upper bound on minutes
int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
int wait_time = mid * s; // convert minutes to seconds
if (can_escape(wait_time)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << "\n";
return 0;
}
