#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e12;
const ll MAXN=805;
/*
Multi-source bfs from all the hives to find out at which seconds every square isn't reachable
Now we want to find path from M to D.
For every second, we first have the bear move S squares then the bees
So given we go from time (for the bear its 1/s seconds each time and move 1 square) t*s to (t+1)*s, bear can only pass through squares with dist>t and ends at a square with dist >t+1
how to solve this now:
bin search on the starting t and from there bfs only to stuff that we can reach.
*/
ll n, s, sx, sy, ex, ey, db[MAXN][MAXN], dm[MAXN][MAXN], dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};
char grid[MAXN][MAXN];
queue<ll> q1, q2;
void bfsBees()
{
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
db[i][j]=INF;
if (grid[i][j]=='H')
{
db[i][j]=0;
q1.push(i);
q2.push(j);
}
}
}
while (!q1.empty())
{
ll x=q1.front(), y=q2.front();
q1.pop();
q2.pop();
for (int i=0; i<4; i++)
{
ll r=x+dx[i], c=y+dy[i];
if (r>=0 && r<n && c>=0 && c<n && db[r][c]==INF && (grid[r][c]=='M' || grid[r][c]=='H' || grid[r][c]=='G'))
{
db[r][c]=db[x][y]+1;
q1.push(r);
q2.push(c);
}
}
}
}
bool works(ll t)
{
if (t>=db[sx][sy])
{
return 0;
}
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
dm[i][j]=INF;
}
}
dm[sx][sy]=s*t;
q1.push(sx);
q2.push(sy);
while (!q1.empty())
{
ll x=q1.front(), y=q2.front();
q1.pop();
q2.pop();
for (int i=0; i<4; i++)
{
ll r=x+dx[i], c=y+dy[i];
if (r>=0 && r<n && c>=0 && c<n && dm[r][c]==INF && (grid[r][c]=='M' || grid[r][c]=='D' || grid[r][c]=='G') && db[r][c]>(dm[x][y]+1)/s)
{
dm[r][c]=dm[x][y]+1;
q1.push(r);
q2.push(c);
}
}
}
return dm[ex][ey]!=INF;
}
int main()
{
cin >> n >> s;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
cin >> grid[i][j];
if (grid[i][j]=='M')
{
sx=i;
sy=j;
}
if (grid[i][j]=='D')
{
ex=i;
ey=j;
}
}
}
bfsBees();
/*for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
cout << (db[i][j]==INF ? -1:db[i][j]) << " ";
}
cout << "\n";
}
cout << "\n";*/
if (!works(0))
{
cout << "-1\n";
return 0;
}
/*for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
cout << (dm[i][j]==INF ? -1:dm[i][j]) << " ";
}
cout << "\n";
}
cout << "\n";*/
ll l=0, r=1e8, mid;
while (l<r)
{
mid=(l+r+1)/2;
if (works(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
cout << l << "\n";
}
