#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;
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();
if(node.first!=0){
if((grid[node.first-1][node.second]=='G'&&!seen_bear[node.first-1][node.second]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first-1][node.second])||grid[node.first-1][node.second]=='D'){
seen_bear[node.first-1][node.second] = true;
bear_dist[node.first-1][node.second] = bear_dist[node.first][node.second]+1;
b.push_back(make_pair(node.first-1,node.second));
}
}
if(node.second!=0){
if((grid[node.first][node.second-1]=='G'&&!seen_bear[node.first][node.second-1]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first][node.second-1])||grid[node.first][node.second-1]=='D'){
seen_bear[node.first][node.second-1] = true;
bear_dist[node.first][node.second-1] = bear_dist[node.first][node.second]+1;
b.push_back(make_pair(node.first,node.second-1));
}
}
if(node.first!=n-1){
if((grid[node.first+1][node.second]=='G'&&!seen_bear[node.first+1][node.second]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first+1][node.second])||grid[node.first+1][node.second]=='D'){
seen_bear[node.first+1][node.second] = true;
bear_dist[node.first+1][node.second] = bear_dist[node.first][node.second]+1;
b.push_back(make_pair(node.first+1,node.second));
}
}
if(node.second!=n-1){
if((grid[node.first][node.second+1]=='G'&&!seen_bear[node.first][node.second+1]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first][node.second+1])||grid[node.first][node.second+1]=='D'){
seen_bear[node.first][node.second+1] = true;
bear_dist[node.first][node.second+1] = bear_dist[node.first][node.second]+1;
b.push_back(make_pair(node.first,node.second+1));
}
}
}
}
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();
if(node.first!=0){
if(grid[node.first-1][node.second]=='G'&&!seen_bees[node.first-1][node.second]){
seen_bees[node.first-1][node.second] = true;
bees_dist[node.first-1][node.second] = bees_dist[node.first][node.second]+1;
a.push_back(make_pair(node.first-1,node.second));
}
}
if(node.second!=0){
if(grid[node.first][node.second-1]=='G'&&!seen_bees[node.first][node.second-1]){
seen_bees[node.first][node.second-1] = true;
bees_dist[node.first][node.second-1] = bees_dist[node.first][node.second]+1;
a.push_back(make_pair(node.first,node.second-1));
}
}
if(node.first!=n-1){
if(grid[node.first+1][node.second]=='G'&&!seen_bees[node.first+1][node.second]){
seen_bees[node.first+1][node.second] = true;
bees_dist[node.first+1][node.second] = bees_dist[node.first][node.second]+1;
a.push_back(make_pair(node.first+1,node.second));
}
}
if(node.second!=n-1){
if(grid[node.first][node.second+1]=='G'&&!seen_bees[node.first][node.second+1]){
seen_bees[node.first][node.second+1] = true;
bees_dist[node.first][node.second+1] = bees_dist[node.first][node.second]+1;
a.push_back(make_pair(node.first,node.second+1));
}
}
}
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';
}
