#include <bits/stdc++.h>
using namespace std;
char board[801][801];
int beeDist[801][801];
int mechoDist[801][801];
int n, s;
pair<int, int> home, mecho;
vector<pair<int, int> > hives;
bool canEscapeAfter(int a) {
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
mechoDist[i][j] = -1;
}
}
queue<pair<int, int> > q;
q.push(mecho);
mechoDist[mecho.first][mecho.second] = s * a;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == home.first and y == home.second)
{
return true;
}
if (mechoDist[x][y]/s >= beeDist[x][y])
{
continue;
}
if (0 <= x+1 and x+1 < n)
{
if (board[x+1][y] == 'G' or board[x+1][y] == 'D')
{
if (mechoDist[x+1][y] == -1)
{
mechoDist[x+1][y] = mechoDist[x][y] + 1;
q.push({x+1, y});
}
}
}
if (0 <= x-1 and x-1 < n)
{
if (board[x-1][y] == 'G' or board[x-1][y] == 'D')
{
if (mechoDist[x-1][y] == -1)
{
mechoDist[x-1][y] = mechoDist[x][y] + 1;
q.push({x-1, y});
}
}
}
if (0 <= y+1 and y+1 < n)
{
if (board[x][y+1] == 'G' or board[x][y+1] == 'D')
{
if (mechoDist[x][y+1] == -1)
{
mechoDist[x][y+1] = mechoDist[x][y] + 1;
q.push({x, y+1});
}
}
}
if (0 <= y-1 and y-1 < n)
{
if (board[x][y-1] == 'G' or board[x][y-1] == 'D')
{
if (mechoDist[x][y-1] == -1)
{
mechoDist[x][y-1] = mechoDist[x][y] + 1;
q.push({x, y-1});
}
}
}
}
return false;
}
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> board[i][j];
beeDist[i][j] = -1;
if (board[i][j] == 'H')
{
hives.push_back({i,j});
}
if (board[i][j] == 'M')
{
mecho = {i,j};
}
if (board[i][j] == 'D')
{
home = {i,j};
}
}
}
queue<pair<int, int> > bees;
for (auto i : hives)
{
bees.push(i);
beeDist[i.first][i.second] = 0;
}
while (!bees.empty())
{
int x = bees.front().first;
int y = bees.front().second;
bees.pop();
if (0 <= x+1 and x+1 < n)
{
if (board[x+1][y] == 'G' or board[x+1][y] == 'M')
{
if (beeDist[x+1][y] == -1)
{
beeDist[x+1][y] = beeDist[x][y] + 1;
bees.push({x+1, y});
}
}
}
if (0 <= x-1 and x-1 < n)
{
if (board[x-1][y] == 'G' or board[x-1][y] == 'M')
{
if (beeDist[x-1][y] == -1)
{
beeDist[x-1][y] = beeDist[x][y] + 1;
bees.push({x-1, y});
}
}
}
if (0 <= y+1 and y+1 < n)
{
if (board[x][y+1] == 'G' or board[x][y+1] == 'M')
{
if (beeDist[x][y+1] == -1)
{
beeDist[x][y+1] = beeDist[x][y] + 1;
bees.push({x, y+1});
}
}
}
if (0 <= y-1 and y-1 < n)
{
if (board[x][y-1] == 'G' or board[x][y-1] == 'M')
{
if (beeDist[x][y-1] == -1)
{
beeDist[x][y-1] = beeDist[x][y] + 1;
bees.push({x, y-1});
}
}
}
}
int regionStart = 0;
int regionEnd = beeDist[mecho.first][mecho.second] - 1;
//cout << "End on " << regionEnd << "\n";
int ans = -1;
while (regionStart <= regionEnd)
{
int med = (regionStart + regionEnd)/2;
// cout << "Checking " << med << "\n";
if (canEscapeAfter(med))
{
ans = med;
regionStart = med + 1;
// cout << "Works\n";
}
else
{
regionEnd = med - 1;
// cout << "Does'nt work\n";
}
}
cout << ans << "\n";
}
