#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
/*
precalcula p grid o tempo que cada célula leva até ser ocupada por abelhas
binary search no tempo
p verificar se tempo x é válido:
floodfill do mecho começando no tempo x e ignorando s:
continuar só se (dist[i][j]+s-1)/s + x < bee[i][j] ou se (dist[i][j]+s-1)/s + x == bee[i][j] e se nn for o último movimento, = dist[i][j]%s != 0
*/
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;
const int MAXN = 800+10;
bool g[MAXN][MAXN];
int bs[MAXN][MAXN]; // bs=bees
int d[MAXN][MAXN]; // distance (mecho)
int aux[4] = {1, -1, 0, 0};
signed main(){
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
// cout << fixed << setprecision(12);
int n, s;
cin >> n >> s;
char x;
pii st = {0,0}, en = {0,0};
queue<pii> bq;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){
cin >> x;
g[i][j] = (x=='G' || x=='M');
bs[i][j] = 1e9;
if (x=='H'){
bq.emplace(i,j);
bs[i][j] = 0;
}
else if (x =='M') st = {i,j};
else if (x == 'D') en = {i, j};
}
while (!bq.empty()){
pii u = bq.front();
bq.pop();
int nd = bs[u.first][u.second]+1;
for (int a=0,b=3;a<4;a++,b--){
int ni = u.first+aux[a], nj = u.second+aux[b];
if (bs[ni][nj] == 1e9 && g[ni][nj]){
bs[ni][nj] = nd;
bq.emplace(ni, nj);
}
}
}
g[en.first][en.second] = g[st.first][st.second] = 1;
bool tru = 0;
int in = 0, fi = 1e9, me;
while (in<=fi){
me = (in+fi)/2;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i][j] = 1e9;
d[st.first][st.second] = 0;
queue<pii> mq;
mq.push(st);
while (!mq.empty()){
pii u = mq.front();
mq.pop();
int nd = d[u.first][u.second]+1;
for (int a=0,b=3;a<4;a++,b--){
int ni = u.first+aux[a], nj = u.second+aux[b];
if (!g[ni][nj] || d[ni][nj] != 1e9) continue;
if (me + (nd+s-1)/s < bs[ni][nj] || (me + (nd+s-1)/s == bs[ni][nj] && nd%s != 0)){
d[ni][nj] = nd;
mq.emplace(ni, nj);
}
}
}
if (d[en.first][en.second] != 1e9){
tru=1, in = me+1;
}else fi = me-1;
}
if (!tru) cout << "-1\n";
else cout << in-1 << "\n";
return 0;
}
