#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define sz(x) (int)(x).size()
#define pii pair<int,int>
#define fi first
#define se second
const int MAXN = 800;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
int n, s;
vector<string> forest(MAXN);
queue<array<int, 3>> hives;
pii start;
inline bool inside(int x, int y) {return x >= 0 && x < n && y >= 0 && y < n;}
inline bool check(int time){
vector<string> t_forest = forest;
queue<array<int, 3>> bees = hives;
queue<array<int, 3>> frontier;
vector<vb> vis(vector<vb>(n, vb(n)));
int minutes = 0;
while(!bees.empty()){
array<int, 3> b = bees.front();
if(b[2] == time)
break;
bees.pop();
for(int i = 0; i < 4; i++){
int new_x = b[0] + dx[i];
int new_y = b[1] + dy[i];
if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'M')){
bees.push({new_x, new_y, b[2] + 1});
t_forest[new_x][new_y] = 'H';
}
}
if(t_forest[start.fi][start.se] == 'H')
return false;
}
frontier.push({start.fi, start.se, 0});
vis[start.fi][start.se] = true;
while(!frontier.empty()){
minutes++;
while(frontier.front()[2] < s * minutes && !frontier.empty()){
array<int, 3> c = frontier.front();
frontier.pop();
if(t_forest[c[0]][c[1]] == 'H') continue;
for(int j = 0; j < 4; j++){
int new_x = c[0] + dx[j];
int new_y = c[1] + dy[j];
if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'D') && !vis[new_x][new_y]){
if(t_forest[new_x][new_y] == 'D'){
return true;
}
frontier.push({new_x, new_y, c[2] + 1});
vis[new_x][new_y] = true;
}
}
}
int size = sz(bees);
while(size--){
array<int, 3> b = bees.front();
bees.pop();
for(int i = 0; i < 4; i++){
int new_x = b[0] + dx[i];
int new_y = b[1] + dy[i];
if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'M')){
bees.push({new_x, new_y, b[2] + 1});
t_forest[new_x][new_y] = 'H';
}
}
}
}
return false;
}
int binary_search(){
int le = 0, ri = n * n;
while(le <= ri){
int mid = le + ((ri - le) >> 1);
if(check(mid)){
le = mid + 1;
}
else{
ri = mid - 1;
}
}
return le - 1;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++){
cin >> forest[i];
for(int j = 0; j < n; j++){
if(forest[i][j] == 'H')
hives.push({i, j, 0});
else if(forest[i][j] == 'M')
start = {i, j};
}
}
cout << binary_search();
return 0;
}
