#include<bits/stdc++.h>
#define int long long int
#define f first
// #define s second
using namespace std;
int di[4] = {0, 0, 1, -1};
int dj[4] = {-1, 1, 0, 0};
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, s;
cin >> n >> s;
vector<string> mat(n, "");
vector<vector<int>> time(n, vector<int>(n, INT_MAX));
int si, sj, ei, ej;
queue<pair<int,pair<int,int>>> bag;
vector<vector<bool>> v(n, vector<bool>(n, 0));
for (int i = 0 ; i < n ; i++) cin >> mat[i];
// cout << -1;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (mat[i][j] == 'M') {
si = i;
sj = j;
} else if (mat[i][j] == 'D') {
ei = i;
ej = j;
} else if (mat[i][j] == 'H') {
bag.push({0, {i, j}});
v[i][j] = 1;
}
}
}
while(!bag.empty()) {
int cnt = bag.front().first;
int i = bag.front().second.first;
int j = bag.front().second.second;
bag.pop();
for (int d = 0 ; d < 4 ; d++) {
int nxi = i + di[d];
int nxj = j + dj[d];
if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T' && mat[nxi][nxj] != 'D') {
if (v[nxi][nxj]) continue;
bag.push({cnt+1, {nxi, nxj}});
v[nxi][nxj] = 1;
time[nxi][nxj] = cnt+1;
}
}
}
// for (int i = 0 ; i < n ; i++) {
// for (int j = 0 ; j < n ; j++) cout << time[i][j] << ' ';
// cout << endl;
// }
int l = 0;
int r = 1e9;
// bool valid = 0;
vector<int> validarr(n*n, 0);
int ans = 1e9;
while(l < r) {
int mid = (l+r+1)/2;
// cout << mid << endl;
bool valid = 0;
if (mid >= time[si][sj]) r = mid-1;
else {
while(!bag.empty()) {
bag.pop();
}
bag.push({mid*s, {si, sj}});
v.resize(0);
v.resize(n, vector<bool>(n, 0));
v[si][sj] = 1;
// cout << bag.size() << endl;
while(!bag.empty()) {
int cnt = bag.front().first;
int i = bag.front().second.first;
int j = bag.front().second.second;
// cout << i << ' ' << j << ' ' << cnt << endl;
bag.pop();
if (i == ei && j == ej) {
valid = 1;
validarr[mid] = 1;
break;
}
for (int d = 0 ; d < 4 ; d++) {
int nxi = i + di[d];
int nxj = j + dj[d];
if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T') {
if (!v[nxi][nxj] && (cnt+1) < time[nxi][nxj]*s) {
bag.push({cnt+1, {nxi, nxj}});
v[nxi][nxj] = 1;
}
}
}
}
if (!valid) r = mid-1;
else l = mid;
}
}
// if (ans == 1e9) cout << -1;
// else cout << l;
if (validarr[l]) cout << l;
else cout << -1;
}
