#include <bits/stdc++.h>
using namespace std;
int nx[4]={1, -1, 0, 0}, ny[4]={0, 0, 1, -1};
char grid[2000][2000]; bool vis[2000][2000];
int d[2000][2000]; int n, s, sx, sy, hx, hy;
bool bfs(int v)
{
if(v*s>=d[sx][sy]) return false;
memset(vis, 0, sizeof vis);
deque<pair<int, pair<int, int>>>q;
q.push_back(make_pair(v*s, make_pair(sx, sy)));
vis[sx][sy]=true;
while(!q.empty()) {
int dis=q.front().first;
int a=q.front().second.first, b=q.front().second.second;
q.pop_front();
if(grid[a][b]=='D') return true;
for(int l=0;l<4;l++) {
int x=a+nx[l], y=b+ny[l];
if(x>=0&&x<n&&y>=0&&y<n) {
if(grid[x][y]!='T'&&dis+1<d[x][y]&&!vis[x][y]) {
q.push_back(make_pair(dis+1, make_pair(x, y)));
vis[x][y]=true;
}
}
}
}
return false;
}
int main()
{
cin>>n>>s;
deque<pair<int, int>>q;
memset(d, -1, sizeof(d));
for(int l=0;l<n;l++) {
for(int i=0;i<n;i++)
{
cin>>grid[l][i];
if(grid[l][i]=='H') {
q.push_back(make_pair(l, i));
d[l][i]=0;
}
else if(grid[l][i]=='M') {
sx=l; sy=i; grid[l][i]='G';
}
else if(grid[l][i]=='D') {
hx=l; hy=i;
}
}
}
while(!q.empty()) {
int a=q.front().first, b=q.front().second; q.pop_front();
for(int l=0;l<4;l++) {
int x=a+nx[l], y=b+ny[l];
if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]=='G'&&d[x][y]==-1) {
d[x][y]=d[a][b]+s; q.push_back(make_pair(x, y));
}
}
}
d[hx][hy]=n*n*s;
int lo=-1, hi=2*n*n;
while(hi-lo>1) {
int mid=(hi+lo)/2;
if(bfs(mid)) lo=mid;
else hi=mid;
}
cout<<lo<<'\n';
return 0;
}
