#include<bits/stdc++.h>
using namespace std;
int n,speed,bees_dist[805][805],bear_dist[805][805];
char grid[805][805];
bool seen_bees[805][805],seen_bear[805][805];
pair<int,int> start,home,dirs[4] = {make_pair(0,1),make_pair(0,-1),make_pair(1,0),make_pair(-1,0)};
vector<pair<int,int> > hives;
deque<pair<int,int> > a;
void thing(){
for(int i=0; i<805; i++){
for(int j=0; j<805; j++){
bear_dist[i][j] = 0;
seen_bear[i][j] = false;
}
}
}
void thing2(int x){
deque<pair<int,int> > b;
b.push_back(start);
seen_bear[start.first][start.second] = true;
while(!b.empty()){
pair<int,int> node = b.front();
b.pop_front();
for(auto d : dirs){
int newx = newx, newy = newy;
if(0<=newx&&newx<n&&0<=newy&&newy<n){
if((grid[newx][newy]=='G'&&!seen_bear[newx][newy]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[newx][newy])||grid[newx][newy]=='D'){
seen_bear[newx][newy] = true;
bear_dist[newx][newy] = bear_dist[node.first][node.second]+1;
b.push_back(make_pair(newx,newy));
}
}
}
}
}
bool poss(int x){
thing();
thing2(x);
if(seen_bear[home.first][home.second]&&bear_dist[home.first][home.second]!=0) return true;
else return false;
}
int main(){
cin >> n >> speed;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> grid[i][j];
if(grid[i][j]=='H') hives.push_back(make_pair(i,j));
else if(grid[i][j]=='M') start = make_pair(i,j);
else if(grid[i][j]=='D') home = make_pair(i,j);
}
}
for(auto hive : hives){
a.push_back(hive);
seen_bees[hive.first][hive.second] = true;
}
while(!a.empty()){
pair<int,int> node = a.front();
a.pop_front();
for(auto d : dirs){
int newx = newx, newy = newy;
if(0<=newx&&newx<n&&0<=newy&&newy<n){
if((grid[newx][newy]=='G'||grid[newx][newy]=='M')&&!seen_bees[newx][newy]){
seen_bees[newx][newy] = true;
bees_dist[newx][newy] = bees_dist[node.first][node.second]+1;
a.push_back(make_pair(newx,newy));
}
}
}
}
if(!poss(0)){
cout << "-1\n";
return 0;
}
int low = 0, high = 1000000,ans=0;
while(low<=high){
int mid = (low+high)/2;
if(poss(mid)){
ans = mid;
low = mid+1;
}else high = mid-1;
}
cout << ans << '\n';
}
