#include <bits/stdc++.h>
using namespace std;
#define ll int
#define vi vector<ll>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1e9;
ll n, s;
string a[810];
ll ti[810][810];
bool vis[810][810];
pr st, de;
pr operator+(pr p1, pr p2) {
return {p1.ff+p2.ff, p1.ss+p2.ss};
}
vector<pr> m4 = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool isValid(pr p) {
if (p.ff < 0 || p.ss < 0 || p.ff >= n || p.ss >= n || a[p.ff][p.ss] == 'T') return false;
return true;
}
bool check(int tm) {
if (tm >= ti[st.ff][st.ss]) return false;
queue<tuple<pr, ll>> q;
memset(vis, 0, sizeof(vis));
q.push({st, s*(tm)});
bool f = false;
vector<vi> k(n, vi(n));
while (!q.empty()) {
auto [e, i] = q.front(); q.pop();
if (vis[e.ff][e.ss]) continue;
vis[e.ff][e.ss] = true;
k[e.ff][e.ss] = (i+s-1)/s;
ll ni = i+1;
for (auto d : m4) {
pr m = d+e;
if (vis[m.ff][m.ss] || !isValid(m) || ni/s >= ti[m.ff][m.ss]) continue;
q.push({m, ni});
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << k[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
return vis[de.ff][de.ss];
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> s;
for (int i = 0; i < n; i++) cin >> a[i];
queue<pair<pr, ll>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'H') {
q.push({{i,j}, 0});
}
if (a[i][j] == 'M') {
st = {i, j};
}
if (a[i][j] == 'D') {
vis[i][j] = true;
ti[i][j] = inf+10;
de = {i, j};
}
}
}
while (!q.empty()) {
auto [e, t] = q.front(); q.pop();
if (vis[e.ff][e.ss]) continue;
vis[e.ff][e.ss] = true;
ti[e.ff][e.ss] = t;
for (auto d : m4) {
pr m = e+d;
if (!isValid(m) || vis[m.ff][m.ss]) continue;
q.push({m, t+1});
}
}
ll i = -1, j = 650000;
ll ans = -1;
while (i <= j) {
ll mid = (i + j)/2;
if (check(mid)) {
ans = mid;
i = mid+1;
} else {
j = mid-1;
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << ti[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
// cout << check(1) << endl;
cout << ans << endl;
return 0;
}
