#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <stdio.h> /* printf, scanf, puts, NULL */
#include <stdlib.h> /* srand, rand */
#include <time.h>
#include <unordered_map>
#include <string>
#include <fstream>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Mat = vector<vector<ll>>;
const ll MOD = 2019201997LL;
const ll FACTOR1 = 2019201913LL;
const ll FACTOR2 = 2019201949LL;
const int MAXN = 1e3 + 11;
int n, s, l, r;
char t[MAXN][MAXN];
vector<pair<int,int>>hives;
int dx[]{ 0,0,-1,1 };
int dy[]{ 1,-1,0,0 };
int dist[MAXN][MAXN];
pair<int, int> bear,house;
bool within(int x, int y)
{
return (x >= 0 && y >= 0 && x < n&& y < n);
}
bool reached(int mecho, int bees)
{
return mecho / s < bees;
}
void action()
{
queue<pair<int, int>> q;
vector<vector<int>> vis(n, vector<int>(n));
for (auto h : hives)
{
q.push(h);
vis[h.first][h.second] = true;
}
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int d = 0; d < 4; d++)
{
int newX = x + dx[d];
int newY = y + dy[d];
if (!within(newX, newY) || (t[newX][newY] != 'G' && t[newX][newY] != 'M')
|| vis[newX][newY])
continue;
vis[newX][newY] = true;
q.push({ newX,newY });
dist[newX][newY] = dist[x][y] + 1;
}
}
}
bool check(int mins)
{
queue<pair<int,int>> q;
vector<vector<int>>bear_dist(n, vector<int>(n));
vector<vector<int>> vis(n, vector<int>(n));
q.push(bear);
vis[bear.first][bear.second] = true;
if (dist[bear.first][bear.second] <= mins)
q.pop();
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
//cout << x << " " << y << " " << bear_dist[x][y] <<" VS "<<
// dist[x][y]<<'\n';
for (int d = 0; d < 4; d++)
{
int newX = x + dx[d];
int newY = y + dy[d];
if (!within(newX, newY) || (t[newX][newY] != 'G' && t[newX][newY] != 'M') || (
!reached(bear_dist[x][y]+1,dist[newX][newY]-mins)) || vis[newX][newY])
continue;
vis[newX][newY] = true;
q.push({ newX,newY });
bear_dist[newX][newY] = bear_dist[x][y] + 1;
}
}
int flag = 0;
for (int d = 0; d < 4; d++)
{
int Hx = house.first + dx[d];
int Hy = house.second + dy[d];
if (!within(Hx, Hy) || (t[Hx][Hy] != 'G' && t[Hx][Hy]!='M'))
continue;
if (vis[Hx][Hy] && reached(bear_dist[Hx][Hy],dist[Hx][Hy]-mins))
flag = 1;
}
return flag;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
//freopen("lasers.in", "r", stdin);
//freopen("lasers.out", "w", stdout);
cin >> n >> s;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> t[i][j];
if (t[i][j] == 'H')
hives.push_back({ i,j });
if (t[i][j] == 'M')
bear = { i,j };
if (t[i][j] == 'D')
house = { i,j };
}
}
action();
int l = 0, r = n * n;
while (l < r)
{
int m = (l + r + 1) / 2;
if (check(m))
l = m;
else
r = m - 1;
}
if (l == n * n)
cout << -1 << '\n';
else
cout << l << '\n';
return 0;
}
