#include "bits/stdc++.h"
using namespace std;
int main() {
int n, s;
cin >> n >> s;
vector<vector<char>> board(n, vector<char>(n));
vector<pair<int, int>> hives;
pair<int, int> mecho;
pair<int, int> home;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
if (board[i][j] == 'H') {
hives.push_back({i, j});
} else if (board[i][j] == 'M') {
mecho = {i, j};
} else if (board[i][j] == 'D') {
home = {i, j};
}
}
}
vector<vector<int>> hive_dist(n, vector<int>(n, 1e8));
vector<vector<bool>> hive_visited(n, vector<bool>(n, false));
queue<pair<int, int>> hive_queue;
for (auto hive : hives) {
hive_queue.push(hive);
hive_dist[hive.first][hive.second] = 0;
hive_visited[hive.first][hive.second] = true;
}
vector<pair<int, int>> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!hive_queue.empty()) {
pair<int, int> curr_hive = hive_queue.front();
hive_queue.pop();
for (auto move : moves) {
pair<int, int> next_hive = {curr_hive.first + move.first, curr_hive.second + move.second};
if (0 <= next_hive.first && 0 <= next_hive.second && next_hive.first < n && next_hive.second < n) {
if (!hive_visited[next_hive.first][next_hive.second]) {
if (board[next_hive.first][next_hive.second] != 'T' && board[next_hive.first][next_hive.second] != 'D') {
hive_dist[next_hive.first][next_hive.second] = hive_dist[curr_hive.first][curr_hive.second] + 1;
hive_queue.push({next_hive.first, next_hive.second});
hive_visited[next_hive.first][next_hive.second] = true;
}
}
}
}
}
int lo = -1, hi = 10000000;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
vector<vector<int>> mecho_dist(n, vector<int>(n, 1e8));
vector<vector<bool>> mecho_visited(n, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push(mecho);
mecho_dist[mecho.first][mecho.second] = 0;
mecho_visited[mecho.first][mecho.second] = true;
bool valid = false;
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
if (p == home) {
valid = true;
break;
}
for (pair<int, int> move : moves) {
pair<int, int> next_p = {p.first + move.first, p.second + move.second};
if (0 <= next_p.first && next_p.first < n && 0 <= next_p.second && next_p.second < n) {
if (!mecho_visited[next_p.first][next_p.second]) {
if (board[next_p.first][next_p.second] != 'T' && board[next_p.first][next_p.second] != 'H') {
if (hive_dist[next_p.first][next_p.second] - mid > (mecho_dist[p.first][p.second]+1) / s) {
q.push(next_p);
mecho_dist[next_p.first][next_p.second] = mecho_dist[p.first][p.second] + 1;
mecho_visited[next_p.first][next_p.second] = true;
}
}
}
}
}
}
if (valid) {
lo = mid;
} else {
hi = mid - 1;
}
}
cout << lo << endl;
}
