#include<bits/stdc++.h>
using namespace std;
int t,n,u,v,s,xs,ys,ans = -1;
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
char source[805][805],c[805][805];
string str;
queue<pair<int,int> > mecho,bee;
vector<pair<int,int> > b,m;
int main()
{
cin >> n >> s;
for(int i = 1;i <= n;i++)
{
cin >> str;
for(int j = 1;j <= n;j++)
{
source[i][j] = str[j-1];
if(source[i][j] == 'M') xs = i,ys = j;
}
}
for(int d = 1e5;d >= 1;d /= 2)
{
while(true)
{
t = ans+d;
int ok = 0;
m.clear();
b.clear();
while(!mecho.empty()) mecho.pop();
while(!bee.empty()) bee.pop();
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
c[i][j] = source[i][j];
if(c[i][j] == 'H') bee.push({i,j});
}
mecho.push({xs,ys});
for(int i = 1;i <= t;i++)
{
b.clear();
while(!bee.empty())
{
b.push_back(bee.front());
bee.pop();
}
for(auto x:b)
{
tie(u,v) = x;
for(int j = 0;j < 4;j++)
{
int nu = u+dx[j],nv = v+dy[j];
if(nu < 1||nu > n||nv < 1||nv > n) continue;
if(!(c[nu][nv] == 'M'||c[nu][nv] == 'G')) continue;
bee.push({nu,nv});
c[nu][nv] = 'H';
}
}
}
while(!mecho.empty())
{
for(int i = 1;i <= s;i++)
{
m.clear();
if(mecho.empty()) break;
while(!mecho.empty())
{
tie(u,v) = mecho.front();
if(c[u][v] == 'M')
m.push_back(mecho.front());
mecho.pop();
}
for(auto y:m)
{
tie(u,v) = y;
for(int j = 0;j < 4;j++)
{
int nu = u+dx[j],nv = v+dy[j];
if(nu < 1||nu > n||nv < 1||nv > n) continue;
if(!(c[nu][nv] == 'G'||c[nu][nv] == 'D')) continue;
if(c[nu][nv] == 'D') ok = 1;
mecho.push({nu,nv});
c[nu][nv] = 'M';
}
}
}
b.clear();
while(!bee.empty())
{
b.push_back(bee.front());
bee.pop();
}
for(auto x:b)
{
tie(u,v) = x;
for(int j = 0;j < 4;j++)
{
int nu = u+dx[j],nv = v+dy[j];
if(nu < 1||nu > n||nv < 1||nv > n) continue;
if(!(c[nu][nv] == 'M'||c[nu][nv] == 'G')) continue;
bee.push({nu,nv});
c[nu][nv] = 'H';
}
}
}
if(ok) ans += d;
else break;
}
}
cout << ans << '\n';
return 0;
}
