#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 800 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
int n, k;
string a[N], b[N];
queue<pair<pii, int>> qu;
void ms_bfs(int t){
while(!qu.empty()) qu.pop();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j] == 'H') qu.push({{i, j}, t});
}
}
while(!qu.empty()){
pii ord = qu.front().fi;
int x = ord.fi, y = ord.se, remain = qu.front().se;
qu.pop();
if(!remain) continue;
for(int dir = 0; dir < 4; dir++){
int u = x + dx[dir], v = y + dy[dir];
if(u < 0 || u >= n || v < 0 || v >= n || b[u][v] != 'G') continue;
b[u][v] = 'H'; qu.push({{u, v}, remain - 1});
}
}
}
vector<pii> mechoo(vector<pii> cur){
vector<pii> tmp;
while(!qu.empty()) qu.pop();
for(pii ord : cur){
int x = ord.fi, y = ord.se;
if(b[x][y] == 'H') continue;
qu.push({{x, y}, k});
}
while(!qu.empty()){
pii ord = qu.front().fi;
int x = ord.fi, y = ord.se, remain = qu.front().se;
qu.pop();
tmp.push_back({x, y});
if(!remain){
continue;
}
for(int dir = 0; dir < 4; dir++){
int u = x + dx[dir], v = y + dy[dir];
if(u < 0 || u >= n || v < 0 || v >= n) continue;
if(b[u][v] != 'G' && b[u][v] != 'D') continue;
b[u][v] = 'M'; qu.push({{u, v}, remain - 1});
}
}
return tmp;
}
bool bfs(){
vector<pii> be1, be2; //bees
vector<pii> me; //mecho
pii en = {-1, -1};
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j] == 'M') me.push_back({i, j});
if(b[i][j] == 'H') be1.push_back({i, j});
if(b[i][j] == 'D') en = {i, j};
}
}
// cout<<"\nMECHOOOO\n";
// for(pii ord : me) cout<<ord.fi<<" "<<ord.se<<'\n';
// cout<<"BEEEEEEEEEEEEEEEES\n";
// for(pii ord : be1) cout<<ord.fi<<" "<<ord.se<<'\n';
// cout<<"HOME "<<en.fi<<" "<<en.se<<'\n';
// return;
while(!me.empty()){
me = mechoo(me);
if(b[en.fi][en.se] == 'M') return 1;
be2.clear();
for(pii ord : be1){
int x = ord.fi, y = ord.se;
for(int dir = 0; dir < 4; dir++){
int u = x + dx[dir], v = y + dy[dir];
if(u < 0 || u >= n || v < 0 || v >= n) continue;
if(b[u][v] != 'M' && b[u][v] != 'G') continue;
b[u][v] = 'H'; be2.push_back({u, v});
}
}
be1.clear(); swap(be1, be2);
// cout<<"----------------------\n";
// for(int i = 0; i < n; i++) cout<<b[i]<<'\n';
}
return 0;
}
bool check(int t){
for(int i = 0; i < n; i++) b[i] = a[i];
ms_bfs(t);
// for(int i = 0; i < n; i++) cout<<b[i]<<'\n';
return bfs();
}
void solve(){
cin>>n>>k;
for(int i = 0; i < n; i++) cin>>a[i];
// cout<<check(1); return;
int l = 0, r = 2 * n, mid;
while(l <= r){
mid = (l + r) >> 1;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
cout<<r;
}
signed main(){
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc = 1;
// cin>>tc;
while(tc--) solve();
}
