#include <bits/stdc++.h>
#define int long long
using namespace std;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1},n,s;
char a[805][805];
bool ob(int px,int py) {
return (px<1 || px>n || py<1 || py>n);
}
int calc(int p) {
int res=(p/s);
if ((p%s)!=0) res++;
return res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("mecho.in","r",stdin);
cin>>n>>s;
int mpx,mpy,hpx,hpy;
vector<pair<int,int>> hives;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
cin>>a[i][j];
if (a[i][j]=='M') {
mpx = i;
mpy = j;
}
else if (a[i][j]=='D') {
hpx = i;
hpy = j;
}
else if (a[i][j]=='H') hives.push_back({i,j});
}
}
auto check=[&](int x) {
if (x<0) return true;
vector<vector<int>> hdis(n+1,vector<int>(n+1,-1));
vector<pair<int,int>> pos;
queue<pair<int,int>> todo;
for (auto [i,j]:hives) {
hdis[i][j] = 0;
todo.push({i,j});
}
while (todo.size()) {
pair<int,int> f=todo.front(); todo.pop();
if (hdis[f.first][f.second]<=x) pos.push_back(f);
for (int i=0;i<4;i++) {
int nx=(f.first+dx[i]),ny=(f.second+dy[i]);
if (ob(nx,ny)||(a[nx][ny]=='T')) continue;
if (hdis[nx][ny]<0) {
hdis[nx][ny] = hdis[f.first][f.second]+1;
todo.push({nx,ny});
}
}
}
vector<vector<int>> tem(n+1,vector<int>(n+1,-1));
for (auto [i,j]:pos) {
tem[i][j] = 0;
todo.push({i,j});
}
while (todo.size()) {
pair<int,int> f=todo.front(); todo.pop();
for (int i=0;i<4;i++) {
int nx=(f.first+dx[i]),ny=(f.second+dy[i]);
if (ob(nx,ny)||(a[nx][ny]=='T')) continue;
if (tem[nx][ny]<0) {
tem[nx][ny] = tem[f.first][f.second]+1;
todo.push({nx,ny});
}
}
}
vector<vector<int>> mdis(n+1,vector<int>(n+1,-1));
vector<vector<bool>> visted(n+2,vector<bool>(n+2,false));
todo.push({mpx,mpy});
mdis[mpx][mpy] = 0;
while (todo.size()) {
pair<int,int> f=todo.front(); todo.pop();
visted[f.first][f.second] = true;
if (calc(mdis[f.first][f.second])>tem[f.first][f.second]) {
mdis[f.first][f.second] = -1;
continue;
}
for (int i=0;i<4;i++) {
int nx=(f.first+dx[i]),ny=(f.second+dy[i]);
if (ob(nx,ny)||(a[nx][ny]=='T')||visted[nx][ny]) continue;
if (mdis[nx][ny]<0) {
mdis[nx][ny] = mdis[f.first][f.second]+1;
todo.push({nx,ny});
}
}
}
return mdis[hpx][hpy]>=0;
} ;
int lo=(-1),hi=100000000000;
while (lo<hi) {
int mid=(lo+hi+1)>>1;
if (check(mid)) lo = mid;
else hi = mid-1;
}
cout<<lo;
return 0;
}
