#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
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];
}
int endx = 0, endy = 0, stx = 0, sty = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'M') {
stx = i;
sty = j;
}
if (a[i][j] == 'D') {
endx = i;
endy = j;
}
}
}
vector<vector<int>> res(n, vector<int>(n, 2e9));
vector<vector<bool>> vis(n, vector<bool>(n));
res[stx][sty] = 0;
queue<pair<int, int>> que;
que.emplace(stx, sty);
while (!que.empty()) {
auto [x, y] = que.front();
vis[x][y] = 1;
que.pop();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (abs(i - x) + abs(j - y) <= s && !vis[i][j] && a[i][j] != 'T') {
res[i][j] = min(res[i][j], res[x][y] + 1);
que.emplace(i, j);
}
}
}
}
auto good = [&](int k) {
queue<array<int, 3>> que;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'H') {
que.push({i, j, 0});
}
}
}
vector<vector<bool>> vis(n, vector<bool>(n));
auto valid = [&](int x, int y) {
return (0 <= x && x < n && 0 <= y && y < n && !vis[x][y] && a[x][y] != 'T' && a[x][y] != 'D');
};
while (!que.empty()) {
auto [x, y, d] = que.front();
vis[x][y] = true;
que.pop();
if (d == k) continue;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny)) {
que.push({nx, ny, d + 1});
}
}
}
vector<vector<int>> dist(n, vector<int>(n, 1e9));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (vis[i][j]) {
dist[i][j] = 0;
q.emplace(i, j);
vis[i][j] = false;
}
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
vis[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny)) {
q.emplace(nx, ny);
dist[nx][ny] = min(dist[nx][ny], dist[x][y] + 1);
}
}
}
fill(vis.begin(), vis.end(), vector<bool>(n, false));
q.emplace(stx, sty);
while (!q.empty()) {
auto [x, y] = q.front();
vis[x][y] = 1;
q.pop();
if (x == endx && y == endy) {
return true;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < n && !vis[nx][ny] && a[nx][ny] != 'T' && dist[nx][ny] > res[nx][ny]) {
q.emplace(nx, ny);
}
}
}
return false;
};
if (!good(0)) {
cout << -1 << '\n';
return 0;
}
int l = 0, r = 1e9;
while (l + 1 < r) {
int m = (l + r) / 2;
if (good(m)) {
l = m;
}
else {
r = m;
}
}
cout << l << '\n';
return 0;
}
