#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
char str[801][801];
int dism[801][801],disb[801][801],n,s;
int rm,cm,rd,cd;
vector<pair<int,int>> dir = {{-1,0},{0,-1},{1,0},{0,1}};
queue<tuple<int,int,int>> q;
queue<pair<int,int>> Q;
bool solve(int t) {
if (t>=disb[rm][cm]) return false;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
dism[i][j] = INF;
}
}
dism[rm][cm] = t;
q.push({rm, cm, 0});
while (!q.empty()) {
auto [x,y,cou] = q.front(); q.pop();
if (dism[x][y]==INF) continue;
for(auto [di,dj]:dir) {
int xx = x + di, yy = y + dj;
int next = dism[x][y] + ((cou+1)%s == 0);
if (xx<1 || xx>n || yy<1 || yy>n || str[xx][yy]=='T') continue;
if (next < disb[xx][yy]) {
dism[xx][yy] = next;
q.push({xx, yy, cou+1});
}
}
}
return dism[rd][cd] != INF;
}
int main(){
cin >> n >> s;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
cin >> str[i][j];
dism[i][j] = disb[i][j] = INF;
if (str[i][j]=='M') rm = i, cm = j;
else if (str[i][j]=='D') rd = i, cd = j;
else if (str[i][j]=='H') {
disb[i][j] = 0;
Q.push({i, j});
}
}
}
while (!Q.empty()) {
auto [a,b] = Q.front(); Q.pop();
for(auto [di,dj]:dir) {
int aa = a + di, bb = b + dj;
if (aa<1 || aa>n || bb<1 || bb>n || str[aa][bb]=='T' || str[aa][bb]=='D') continue;
if (disb[aa][bb]>disb[a][b]+1) {
disb[aa][bb] = disb[a][b]+1;
Q.push({aa,bb});
}
}
}
int l=1,r=n*n,ans;
while (l<r) {
int mid = (l + r) / 2;
if (solve(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
cout << ans;
}
