#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const ll mod = 1e9 + 7;
const ll INF = 1e18;
//--------------------------------------------------------------------
void hbmt() {
ll n, s;
cin >> n >> s;
pa M, D;
vector<pa> vbee;
vector<vector<char>> a(n + 1, vector<char> (n + 1, ' '));
vector<vector<ll>> mark(n + 1, vector<ll> (n + 1, 0));
FOR(i, 1, n) {
FOR(j, 1, n) {
cin >> a[i][j];
if(a[i][j] == 'M') {
M = {i, j};
}
else if(a[i][j] == 'H') {
vbee.push_back({i, j});
}
else if(a[i][j] == 'D') {
D = {i, j};
}
}
}
pa mov[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
auto outside = [&] (ll x, ll y) {
return x <= 0 || x > n || y <= 0 || y > n;
};
auto check = [&] (ll x) {
queue<pa> qbee;
queue<pa> q;
q.push(M);
FOR(i, 1, n) FOR(j, 1, n) mark[i][j] = 0;
mark[M.fi][M.se] = 1;
for(auto e : vbee) {
qbee.push(e);
mark[e.fi][e.se] = -1;
}
while(x--) {
ll t = qbee.size();
while(t--) {
pa u = qbee.front();
qbee.pop();
FOR(i, 0, 3) {
pa v = {mov[i].fi + u.fi, mov[i].se + u.se};
if(outside(v.fi, v.se) || a[v.fi][v.se] == 'T' || a[v.fi][v.se] == 'D')
continue;
if(mark[v.fi][v.se] != -1) {
mark[v.fi][v.se] = -1;
qbee.push(v);
}
}
}
}
while(1) {
ll _s = s;
while(_s--) {
ll t = q.size();
while(t--) {
pa u = q.front();
q.pop();
if(mark[u.fi][u.se] == -1) continue;
FOR(i, 0, 3) {
pa v = {mov[i].fi + u.fi, mov[i].se + u.se};
if(outside(v.fi, v.se) || a[v.fi][v.se] == 'T')
continue;
if(mark[v.fi][v.se] == 0) {
mark[v.fi][v.se] = 1;
q.push(v);
}
}
}
}
if(mark[D.fi][D.se] == 1) return true;
if(q.size() == 0) return false;
ll t = qbee.size();
while(t--) {
pa u = qbee.front();
qbee.pop();
FOR(i, 0, 3) {
pa v = {mov[i].fi + u.fi, mov[i].se + u.se};
if(outside(v.fi, v.se) || a[v.fi][v.se] == 'T' || a[v.fi][v.se] == 'D')
continue;
if(mark[v.fi][v.se] != -1) {
mark[v.fi][v.se] = -1;
qbee.push(v);
}
}
}
}
return false;
};
ll l = 0, r = n * n;
ll res = -1;
while(l <= r) {
ll mid = l + r >> 1;
if(check(mid)) {
l = mid + 1;
res = mid;
}
else r = mid - 1;
}
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#define NAME "hbmt"
if(fopen(NAME".inp", "r")) {
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
//int t;cin>>t;while(t--)
hbmt();
return 0;
}
