#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>
#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>
#define IO (std::string) ""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");
#define NMAX 1000
#define INF INT_MAX
int n, s;
char map[NMAX][NMAX];
pii start, finish;
std::vector<pii> hives;
std::map<pii, int> d1, d2, d;
int di[]{1, -1, 0, 0}, dj[]{0, 0, 1, -1};
void citire() {
std::cin >> n >> s;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
std::cin >> map[i][j];
if (map[i][j] == 'M')
start = {i, j};
if (map[i][j] == 'D')
finish = {i, j};
if (map[i][j] == 'H')
hives.push_back({i, j});
}
}
bool in(pii coord) {
int i = coord.first, j = coord.second;
return i >= 0 && i < n && j >= 0 && j < n;
}
void bfs(std::queue<pii> &q, std::map<pii, int> &d,
std::function<bool(pii coords)> check) {
while (!q.empty()) {
pii u = q.front();
int i = u.first;
int j = u.second;
q.pop();
for (int k = 0; k < 4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (check({ni, nj}) && d[{ni, nj}] > d[{i, j}] + 1) {
d[{ni, nj}] = d[{i, j}] + 1;
q.push({ni, nj});
}
}
}
}
std::map<pii, bool> vis;
int ans = -1;
void dfs(pii nod, int k, int curr_min) {
vis[nod] = 1;
if (k % s == 0)
curr_min = std::min(curr_min, abs(k / s + 1 - d2[nod]));
if (nod == finish) {
ans = std::max(ans, curr_min);
// for (int i = 0; i <= k; i++)
// std::cout << "{" << a[i].first << "," << a[i].second << "}" << ' ';
// std::cout << '\n';
}
for (int i = 0; i < 4; i++) {
pii nou = {nod.first + di[i], nod.second + dj[i]};
if (!vis[nou] && d2[nou] * s > k + 1 && in(nou) &&
map[nou.first][nou.second] != 'T') {
dfs(nou, k + 1, curr_min);
}
}
vis[nod] = 0;
}
int main() {
std::cin.tie(0)->std::ios::sync_with_stdio(0);
citire();
std::queue<pii> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
d[{i, j}] = d1[{i, j}] = d2[{i, j}] = INF;
}
for (pii it : hives) {
q.push(it);
d2[it] = 0;
}
bfs(q, d2, [&](pii coords) {
return in(coords) && map[coords.first][coords.second] != 'D' &&
map[coords.first][coords.second] != 'T';
});
dfs(start, 0, INF);
std::cout << ans << '\n';
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d2[{i, j}] != INF)
std::cout << d2[{i, j}] << ' ';
else
std::cout << "oo ";
}
std::cout << '\n';
}*/
return 0;
}
