// check ctrl+v :^)
/* Arthur Conmy IOI template - minimal! */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define ff first
#define ss second
#define pb push_back
#define REP(i,a,b) \
for(int i = int(a); i<=int(b); i++)
int grid[802][802]; // 0: tree / boundary
// 1: grass
// 2: hive
// 3: mecho's home
int bee_dis[802][802];
int INF = int(1e9);
pii start;
int n,s;
bool vis[802][802];
bool try_it(int t)
{
vector<pii> BFS = {start};
int cur_dis=0;
while(!BFS.empty())
{
// cout << cur_dis << endl;
if(cur_dis%s == 0 && cur_dis!=0) t++;
vector<pii> new_BFS;
for(auto P:BFS)
{
if(bee_dis[P.ff][P.ss]<=t) continue;
REP(x,-1,1)
{
REP(y,-1,1)
{
// cout << P.ff+x << " " << P.ff+y << endl;
if(vis[P.ff+x][P.ss+y]) continue;
if(abs(x)+abs(y)!=1) continue;
if(bee_dis[P.ff+x][P.ss+y] <= t) continue; // do we need to check that the current square isn't now bad?
if(grid[P.ff+x][P.ss+y] == 3) return true;
if(grid[P.ff+x][P.ss+y] != 1) continue;
new_BFS.pb({P.ff+x,P.ss+y});
vis[P.ff+x][P.ss+y]=1;
}
}
}
BFS=new_BFS;
cur_dis++;
}
return false;
}
int main()
{
#ifdef ARTHUR_LOCAL
ifstream cin("input.txt");
#endif
REP(i,0,801)
{
REP(j,0,801)
{
bee_dis[i][j]=INF;
}
}
cin>>n>>s;
vector<pii> bees;
REP(i,1,n)
{
string row;
cin>>row;
REP(j,1,n)
{
if(row[j-1]=='G') grid[i][j]=1;
if(row[j-1]=='H')
{
grid[i][j]=2;
bees.pb({i,j});
bee_dis[i][j]=0;
}
if(row[j-1]=='M')
{
grid[i][j]=1; // Mecho's start is grassy
start={i,j};
}
if(row[j-1]=='D')
{
grid[i][j]=3;
}
}
}
// precompute bee_dis
while(!bees.empty())
{
vector<pii> new_bees;
for(auto b:bees)
{
REP(x,-1,1)
{
REP(y,-1,1)
{
if(abs(x)+abs(y)!=1) continue;
if(bee_dis[b.ff+x][b.ss+y] != INF) continue;
if(grid[b.ff+x][b.ss+y] != 1) continue;
bee_dis[b.ff+x][b.ss+y]=1+bee_dis[b.ff][b.ss];
new_bees.pb({b.ff+x,b.ss+y});
}
}
}
bees=new_bees;
}
// REP(i,1,n)
// {
// REP(j,1,n)
// {
// if(bee_dis[i][j]==INF)
// {
// cout << "-1 ";
// continue;
// }
// cout << bee_dis[i][j] << " ";
// if(bee_dis[i][j]<10) cout << " ";
// }
// cout << endl;
// }
vis[start.ff][start.ss]=1;
int l=0;
int r=n*n; // bin search parameters
while(l<r)
{
// cout << l << " " << r << endl;
REP(i,0,801)
{
REP(j,0,801)
{
vis[i][j]=0;
}
}
vis[start.ff][start.ss]=1;
int mid=(l+r)/2;
if(try_it(mid))
{
if(l==mid)
{
REP(i,0,801)
{
REP(j,0,801)
{
vis[i][j]=0;
}
}
vis[start.ff][start.ss]=1;
if(try_it(r)) l=r;
else r=l;
}
else l=mid;
}
else
{
r=mid-1;
}
}
REP(i,0,801)
{
REP(j,0,801)
{
vis[i][j]=0;
}
}
vis[start.ff][start.ss]=1;
if(!try_it(0)) cout << -1 << endl;
else cout << l << endl;
}
