#include <bits/stdc++.h>
#define ll long long
#define pi pair<ll, ll>
#define fi first
#define se second
using namespace std;
const int u[] = {0, 1, 0, -1};
const int v[] = {1, 0, -1, 0};
int n, steps;
char grid[805][805];
pi init, home;
vector<pi> honey;
bool check(ll cur, ll dist, ll m)
{
if (cur % steps == 0)
{
return (cur / steps + m < dist);
} else
{
return (cur / steps + m + 1 <= dist);
}
}
bool safe(int u, int v)
{
return (u >= 0 && u < n && v >= 0 && v < n);
}
void solve()
{
cin >> n >> steps;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin >> grid[i][j];
if (grid[i][j] == 'M')
{
init = make_pair(i, j);
}
if (grid[i][j] == 'D')
{
home = make_pair(i, j);
}
if (grid[i][j] == 'H')
{
honey.push_back({i, j});
}
}
}
vector<vector<ll>> dist1(n, vector<ll>(n, -1));
queue<pi> que;
for(pi x : honey)
{
que.push(x);
dist1[x.fi][x.se] = 0;
}
while(!que.empty())
{
pi now = que.front(); que.pop();
int curU = now.fi, curV = now.se;
for(int i=0; i<4; i++)
{
int ux = u[i] + curU, vx = v[i] + curV;
if (safe(ux, vx) && (grid[ux][vx] == 'G' || grid[ux][vx] == 'M') && dist1[ux][vx] == -1)
{
dist1[ux][vx] = dist1[curU][curV] + 1;
que.push({ux, vx});
}
}
}
ll l = 0, r = 1e9;
ll ans = -1;
while(l <= r)
{
ll m = (l + r) >> 1;
que.push(init);
vector<vector<ll>> dis(n, vector<ll>(n, -1));
dis[init.fi][init.se] = 0;
if (m < dist1[init.fi][init.se])
{
while(!que.empty())
{
pi now = que.front(); que.pop();
int curU = now.fi, curV = now.se;
for(int i=0; i<4; i++)
{
int ux = curU + u[i], vx = curV + v[i];
if (ux == home.fi && vx == home.se)
{
dis[ux][vx] = dis[curU][curV] + 1;
break;
}
if (safe(ux, vx) && grid[ux][vx] != 'H' && dis[ux][vx] == -1 && check(dis[curU][curV] + 1, dist1[ux][vx], m))
{
dis[ux][vx] = dis[curU][curV] + 1;
que.push({ux, vx});
}
}
}
}
if (dis[home.fi][home.se] == -1)
{
r = m - 1;
} else
{
ans = m;
l = m + 1;
}
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
