#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
using i64 = int64_t;
const int INF = 1000000007; //998244353;
struct S {
int n, k;
vector<string> a;
vector<pair<int, int>> hives;
pair<int, int> origin, dest;
vector<vector<int>> bdist;
const array<int, 4> dx = {1, -1, 0, 0};
const array<int, 4> dy = {0, 0, 1, -1};
void run() {
cin >> n >> k;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'H') {
hives.push_back({i, j});
} else if (a[i][j] == 'M') {
origin = {i, j};
} else if (a[i][j] == 'D') {
dest = {i, j};
}
}
}
}
void bfs1() {
queue<array<int, 3>> q;
vector<vector<bool>> visited(n, vector<bool>(n, false));
bdist.resize(n, vector<int>(n, INF));
for (auto p : hives) {
q.push({p.first, p.second, 0});
bdist[p.first][p.second] = 0;
visited[p.first][p.second] = true;
}
while (!q.empty()) {
int x = q.front()[0];
int y = q.front()[1];
int d = q.front()[2];
q.pop();
for (int i = 0; i < 4; ++i) {
int x2 = x + dx[i];
int y2 = y + dy[i];
if (ok(x2, y2) && !visited[x2][y2] && a[x2][y2] != 'D') {
q.push({x2, y2, d + 1});
visited[x2][y2] = true;
bdist[x2][y2] = d + 1;
}
}
}
DEBUG(
for (auto arr : bdist) {
PAR(arr);
}
)
PRINT('\n');
}
void bs() {
if (!safe(0)) {
cout << -1 << '\n';
return;
}
int h = n * n, l = 0;
while (h - 1 > l) {
int m = (h + l) / 2;
if (safe(m)) l = m;
else h = m - 1;
}
cout << (safe(h) ? h : l) << '\n';
}
bool safe(int t) {
PV(t);
queue<array<int, 3>> q;
vector<vector<bool>> visited(n, vector<bool>(n, false));
q.push({origin.first, origin.second, 0});
visited[origin.first][origin.second] = true;
if (bdist[origin.first][origin.second] <= t) return false;
while (!q.empty()) {
int x = q.front()[0];
int y = q.front()[1];
int d = q.front()[2];
q.pop();
for (int i = 0; i < 4; ++i) {
int x2 = x + dx[i];
int y2 = y + dy[i];
if (ok(x2, y2) && !visited[x2][y2] && a[x2][y2] != 'H'
&& (d + 1) / k + t < bdist[x2][y2]) {
q.push({x2, y2, d + 1});
visited[x2][y2] = true;
}
}
}
DEBUG(
for (auto arr : visited) {
PAR(arr);
}
)
PRINT('\n');
return visited[dest.first][dest.second];
}
bool ok(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 'T';
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
auto sol = make_unique<S>();
sol->run();
sol->bfs1();
sol->bs();
}
