#include <bits/stdc++.h>
int n, s;
std::vector <std::string> g;
std::vector <std::vector <int>> bee;
bool ff(int val) {
std::vector <std::vector <int>> bear(n, std::vector <int> (n, 1e9));
int endX, endY;
std::queue <std::pair <int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 'D') endX = j, endY = i;
if (g[i][j] == 'M') {
bear[i][j] = 0;
q.push({ j, i });
}
}
}
if (val >= bee[q.front().second][q.front().first]) return false;
while (q.size()) {
auto now = q.front(); q.pop();
int x = now.first, y = now.second;
if (x + 1 >= 0 && y >= 0 && x + 1 < n && y < n && g[y][x + 1] != 'T' && bear[y][x + 1] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y][x + 1]) q.push({ x + 1, y }), bear[y][x + 1] = bear[y][x] + 1;
if (x >= 0 && y + 1 >= 0 && x < n && y + 1 < n && g[y + 1][x] != 'T' && bear[y + 1][x] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y + 1][x]) q.push({ x, y + 1 }), bear[y + 1][x] = bear[y][x] + 1;
if (x - 1 >= 0 && y >= 0 && x - 1 < n && y < n && g[y][x - 1] != 'T' && bear[y][x - 1] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y][x - 1]) q.push({ x - 1, y }), bear[y][x - 1] = bear[y][x] + 1;
if (x >= 0 && y - 1 >= 0 && x < n && y - 1 < n && g[y - 1][x] != 'T' && bear[y - 1][x] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y - 1][x]) q.push({ x, y - 1 }), bear[y - 1][x] = bear[y][x] + 1;
}
return bear[endY][endX] < int(1e9);
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
std::cin >> n >> s;
g.resize(n);
for (auto& x : g) std::cin >> x;
bee.resize(n, std::vector <int> (n, 1e9));
std::queue <std::pair <int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 'H') {
q.push({ j, i });
bee[i][j] = 0;
}
}
}
while (q.size()) {
auto now = q.front(); q.pop();
int x = now.first, y = now.second;
if (x + 1 >= 0 && y >= 0 && x + 1 < n && y < n && bee[y][x + 1] == int(1e9) && g[y][x + 1] != 'T' && g[y][x + 1] != 'D') q.push({ x + 1, y }), bee[y][x + 1] = bee[y][x] + 1;
if (x >= 0 && y + 1 >= 0 && x < n && y + 1 < n && bee[y + 1][x] == int(1e9) && g[y + 1][x] != 'T' && g[y + 1][x] != 'D') q.push({ x, y + 1 }), bee[y + 1][x] = bee[y][x] + 1;
if (x - 1 >= 0 && y >= 0 && x - 1 < n && y < n && bee[y][x - 1] == int(1e9) && g[y][x - 1] != 'T' && g[y][x - 1] != 'D') q.push({ x - 1, y }), bee[y][x - 1] = bee[y][x] + 1;
if (x >= 0 && y - 1 >= 0 && x < n && y - 1 < n && bee[y - 1][x] == int(1e9) && g[y - 1][x] != 'T' && g[y - 1][x] != 'D') q.push({ x, y - 1 }), bee[y - 1][x] = bee[y][x] + 1;
}
int l = -1, r = n * n;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (ff(mid)) l = mid;
else r = mid;
}
std::cout << l << "\n";
}
