#include <bits/stdc++.h>
#define pi pair<int, int>
#define ti tuple<int, int, int>
#define tii tuple<int, int, int, int>
using namespace std;
int n, s, bee[810][810], stx, sty, enx, eny, cx, cy, cs, cdi, l=0, r=1e9, mid;
int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
pi mec[810][810];
vector<pi> hi;
char arr[810][810];
bool solve(int mn) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
mec[i][j] = {1e9, 1e9};
}
}
queue<tii> q;
q.push({stx, sty, 0, 0});
while(q.size()) {
cx = get<0>(q.front());
cy = get<1>(q.front());
cdi = get<2>(q.front());
cs = get<3>(q.front());
q.pop();
if(cs == s) {
cs = 0;
cdi++;
}
if(cx < 1 || cx > n || cy < 1 || cy > n || arr[cx][cy] == 'T' || mec[cx][cy].first <= cdi) continue;
if(mec[cx][cy].first == cdi && mec[cx][cy].second <= cs) continue;
if(cdi+mn >= bee[cx][cy]) continue;
mec[cx][cy] = {cdi, cs};
for(int i=0; i<4; i++) {
q.push({cx+di[i], cy+dj[i], cdi, cs+1});
}
}
return mec[enx][eny].first != 1e9;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
bee[i][j] = 1e9;
cin >> arr[i][j];
if(arr[i][j] == 'M') {
stx = i;
sty = j;
} else if(arr[i][j] == 'D') {
enx = i;
eny = j;
} else if(arr[i][j] == 'H') {
hi.push_back({i, j});
}
}
}
queue<ti> q;
for(auto i: hi) {
q.push({i.first, i.second, 0});
}
while(q.size()) {
cx = get<0>(q.front());
cy = get<1>(q.front());
cdi = get<2>(q.front());
q.pop();
if(cx < 1 || cx > n || cy < 1 || cy > n || arr[cx][cy] == 'T' || arr[cx][cy] == 'D' || bee[cx][cy] <= cdi) continue;
bee[cx][cy] = cdi;
for(int i=0; i<4; i++) {
q.push({cx+di[i], cy+dj[i], cdi+1});
}
}
while(l < r) {
mid = (l+r)>>1;
if(solve(mid)) {
l = mid+1;
} else {
r = mid;
}
}
cout << l-1;
return 0;
}
