#include <bits/stdc++.h>
using namespace std;
const int N=805, inf=1e9;
const int dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
int n, s, dist1[N][N], dist2[N][N], xM, yM, xD, yD;
string mat[N];
struct state{
int times, steps, x, y;
bool operator<(const state other)const{
return times>other.times;
}
};
bool valid(int x,int y){
return x>=0 && x<n && y>=0 && y<n;
}
void bfs(){
queue<pair<int,int>> q;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (mat[i][j]=='H'){
q.push({i,j});
dist1[i][j]=0;
}
}
}
while (q.size()){
auto [x, y]=q.front();
q.pop();
for (int i=0;i<4;i++){
int nx=x+dx[i], ny=y+dy[i];
if (valid(nx,ny) && mat[nx][ny]!='T' && mat[nx][ny]!='D' && dist1[nx][ny]>dist1[x][y]+1){
dist1[nx][ny]=dist1[x][y]+1;
q.push({nx,ny});
}
}
}
}
bool mecho_reached(int mecho,int bee){
return mecho/s<bee;
}
bool dijkstra(int sx,int sy,int delay){
queue<pair<int,int>> q;
q.push({sx,sy});
dist2[sx][sy]=0;
if (dist1[sx][sy]<=delay) q.pop();
while (q.size()){
auto [x, y]=q.front();
q.pop();
for (int i=0;i<4;i++){
int nx=x+dx[i], ny=y+dy[i];
if (valid(nx,ny) && dist2[nx][ny]==-1 && (mat[nx][ny]=='G' || mat[nx][ny]=='D')
&& mecho_reached(dist2[x][y]+1, dist1[nx][ny]-delay)){
dist2[nx][ny]=dist2[x][y]+1;
q.push({nx,ny});
}
}
}
bool reached=false;
for (int i=0;i<4;i++){
int nx=xD+dx[i], ny=yD+dy[i];
if (valid(nx,ny) && dist2[nx][ny]!=-1 && mecho_reached(dist2[nx][ny], dist1[nx][ny]-delay)){
reached=true;
}
}
return reached;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>s;
for (int i=0;i<n;i++) cin>>mat[i];
fill(&dist1[0][0],&dist1[0][0]+N*N,inf);
bfs();
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (mat[i][j]=='M'){
xM=i;
yM=j;
}
if (mat[i][j]=='D'){
xD=i;
yD=j;
}
}
}
int l=0, r=n*n, ans=-1;
while (l<=r){
int mid=(l+r)>>1;
fill(&dist2[0][0],&dist2[0][0]+N*N,-1);
if (dijkstra(xM,yM,mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans;
return 0;
}
