#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, S;
cin >> N >> S;
pair<int, int> mecho_init_pos, mecho_home_pos;
vector<pair<int, int>> hives;
vector<string> grid(N);
for (int i = 0; i < N; ++i){
cin >> grid[i];
for (int j = 0; j < N; ++j){
if (grid[i][j] == 'M') mecho_init_pos = {i, j};
if (grid[i][j] == 'D') mecho_home_pos = {i, j};
if (grid[i][j] == 'H') hives.push_back({i, j});
}
}
auto adjacent_node = [&](const pair<int, int> &init_pos, bool is_bear) -> vector<pair<int, int>>{
vector<pair<int, int>> adj;
if (init_pos.first > 0 && grid[init_pos.first - 1][init_pos.second] != 'T' && (is_bear || grid[init_pos.first - 1][init_pos.second] != 'D')) adj.push_back({init_pos.first - 1, init_pos.second});
if (init_pos.second > 0 && grid[init_pos.first][init_pos.second - 1] != 'T' && (is_bear || grid[init_pos.first][init_pos.second - 1] != 'D')) adj.push_back({init_pos.first, init_pos.second - 1});
if (init_pos.first < N - 1 && grid[init_pos.first + 1][init_pos.second] != 'T' && (is_bear || grid[init_pos.first + 1][init_pos.second] != 'D')) adj.push_back({init_pos.first + 1, init_pos.second});
if (init_pos.second < N - 1 && grid[init_pos.first][init_pos.second + 1] != 'T' && (is_bear || grid[init_pos.first][init_pos.second + 1] != 'D')) adj.push_back({init_pos.first, init_pos.second + 1});
return adj;
};
vector<vector<int>> dist_bee(N, vector<int>(N, INT_MAX));
queue<pair<int, int>> frontier_bee;
for (pair<int, int> h : hives){
dist_bee[h.first][h.second] = 0;
frontier_bee.push(h);
}
while (!frontier_bee.empty()){
pair<int, int> curr = frontier_bee.front();
frontier_bee.pop();
for (pair<int, int> nxt : adjacent_node(curr, false)){
if (dist_bee[curr.first][curr.second] + S < dist_bee[nxt.first][nxt.second]){
dist_bee[nxt.first][nxt.second] = dist_bee[curr.first][curr.second] + S;
frontier_bee.push(nxt);
}
}
}
auto check = [&](int res) -> bool{
if (dist_bee[mecho_init_pos.first][mecho_init_pos.second] <= res * S) return false;
bool valid = false;
vector<vector<int>> dist_mecho(N, vector<int>(N, INT_MAX));
queue<pair<int, int>> frontier_mecho;
dist_mecho[mecho_init_pos.first][mecho_init_pos.second] = res * S;
frontier_mecho.push(mecho_init_pos);
while (!frontier_mecho.empty()){
pair<int, int> curr = frontier_mecho.front();
frontier_mecho.pop();
if (curr == mecho_home_pos){
valid = true;
break;
}
for (pair<int, int> nxt : adjacent_node(curr, true)){
if (dist_mecho[curr.first][curr.second] + 1 < dist_mecho[nxt.first][nxt.second] && dist_mecho[curr.first][curr.second] + 1 < dist_bee[nxt.first][nxt.second]){
dist_mecho[nxt.first][nxt.second] = dist_mecho[curr.first][curr.second] + 1;
frontier_mecho.push(nxt);
}
}
}
return valid;
};
int l = 0, r = 640000, ans = -1;
while (l <= r){
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
cout << ans;
return 0;
}
