#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pip = pair<int, pii>;
int n, k;
char mp[805][805];
int si, sj, ei, ej;
int l = 0, r = 805*805, mid;
bool vismech[805][805], visbee[805][805], visfake[805][805];
vector<pii> fakebees;
int di[4] = {0, 0, 1, -1}, dj[4] = {1, -1, 0, 0};
queue<pip> qbee, qmech;
bool doable(int start) {
memset(vismech, 0, sizeof vismech);
memset(visbee, 0, sizeof visbee);
while(!qbee.empty()) qbee.pop();
while(!qmech.empty()) qmech.pop();
//bees move first, start times
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(mp[i][j] == 'H') {
qbee.emplace(0, make_pair(i, j));
}
}
}
while(!qbee.empty() && qbee.front().first <= start) {
auto e = qbee.front(); qbee.pop();
int ci = e.second.first, cj = e.second.second;
if(visbee[ci][cj]) continue;
visbee[ci][cj] = 1;
for(int dir = 0; dir < 4; dir ++) {
int ni = ci + di[dir], nj = cj + dj[dir];
if(ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
if(mp[ni][nj] == 'T' || mp[ni][nj] == 'D') continue;
qbee.emplace(e.first+1, make_pair(ni, nj));
}
}
qmech.emplace(0, make_pair(si, sj));
/*cout << "---\n";
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) cout << visbee[i][j];
cout << '\n';
}
cout << "----\n";*/
//now mecho starts moving
for(int cr=0;cr<=n*n;cr++) {
fakebees.clear();
int curbeecnt = (qbee.empty() ? -69 : qbee.front().first);
while(!qbee.empty() && qbee.front().first == curbeecnt) {
auto e = qbee.front(); qbee.pop();
int ci = e.second.first, cj = e.second.second;
if(visbee[ci][cj]) continue;
visbee[ci][cj] = 1; fakebees.emplace_back(ci, cj);
for(int dir = 0; dir < 4; dir ++) {
int ni = ci + di[dir], nj = cj + dj[dir];
if(ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
if(mp[ni][nj] == 'T' || mp[ni][nj] == 'D') continue;
qbee.emplace(e.first+1, make_pair(ni, nj));
}
}
for(auto &e:fakebees) {visbee[e.first][e.second] = 0; visfake[e.first][e.second] = 1;}
while(!qmech.empty() && qmech.front().first <= 1ll*(cr+1)*k) {
auto e = qmech.front(); qmech.pop();
int ci = e.second.first, cj = e.second.second;
if(visbee[ci][cj]) continue;
if(vismech[ci][cj]) continue;
vismech[ci][cj] = 1;
if(e.first == 1ll*(cr+1)*k && visfake[ci][cj]) continue;
for(int dir = 0; dir < 4; dir++) {
int ni = ci+di[dir], nj = cj+dj[dir];
if(ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
if(mp[ni][nj] == 'T') continue;
qmech.emplace(e.first+1, make_pair(ni, nj));
}
}
for(auto &e:fakebees) {visbee[e.first][e.second] = 1; visfake[e.first][e.second] = 0;}
}
/*cout << start << '\n';
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) cout << vismech[i][j];
cout << '\n';
}*/
return vismech[ei][ej];
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> k;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
cin >> mp[i][j];
if(mp[i][j] == 'M') {
si = i; sj = j;
}
if(mp[i][j] == 'D') {
ei = i; ej = j;
}
}
}
//for(int i=0;i<=10;i++) doable(i); cout << '\n';
while(l <= r) {
mid = (l+r) >> 1;
if(doable(mid)) l = mid+1;
else r = mid-1;
}
cout << r;
}
