#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1e9;
constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, s;
cin >> n >> s;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<int>> d(n, vector<int>(n, inf));
queue<pair<int, int>> q;
pair<int, int> start, end;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'H') {
d[i][j] = 0;
q.emplace(i, j);
}
if (a[i][j] == 'M') {
start = {i, j};
}
if (a[i][j] == 'D') {
end = {i, j};
}
}
}
auto inside = [&](int i, int j) {
return (0 <= i && i < n && 0 <= j && j < n && a[i][j] != 'T');
};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x_nw = x + dx[i];
int y_nw = y + dy[i];
if (inside(x_nw, y_nw) && a[x_nw][y_nw] != 'D' && d[x_nw][y_nw] == inf) {
d[x_nw][y_nw] = d[x][y] + 1;
q.emplace(x_nw, y_nw);
}
}
}
auto good = [&](int k) {
if (k >= d[start.first][start.second]) return false;
queue<array<int, 3>> q;
vector<vector<bool>> vis(n, vector<bool>(n));
q.push({start.first, start.second, 0});
vis[start.first][start.second] = 1;
while (!q.empty()) {
auto [x, y, w] = q.front();
if (x == end.first && y == end.second) {
return true;
}
q.pop();
for (int i = 0; i < 4; i++) {
int x_nw = x + dx[i];
int y_nw = y + dy[i];
if (inside(x_nw, y_nw) && !vis[x_nw][y_nw]) {
if (w / s + k < d[x_nw][y_nw]) {
vis[x_nw][y_nw] = 1;
q.push({x_nw, y_nw, w + 1});
}
}
}
}
return false;
};
if (!good(0)) {
cout << -1 << '\n';
return 0;
}
int l = 0, r = n * n;
while (l + 1 < r) {
int m = (l + r) / 2;
if (good(m)) {
l = m;
} else {
r = m;
}
}
cout << l << '\n';
return 0;
}
