#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<bool>> maps;
vector<vector<int>> distBees;
int n,s;
pair<int, int> home, start;
vector<int> dx = {0,0,1,-1}, dy = {1,-1,0,0};
struct Compare {
bool operator()(tuple<int, int, int> a, tuple<int, int, int> b) {
return get<2>(a)>get<2>(b);
}
};
void print(vector<vector<int>> v) {
for(int i = 0; i < v.size(); i++) {
for(int j = 0; j < v.size(); j++) {
cout << v[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
bool possible(int mid) {
vector<vector<int>> temp = distBees;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) temp[i][j]-=mid;
}
//cout << mid << endl;
//print(temp);
vector<vector<int>> minDist(n, vector<int>(n, 1000000000));
minDist[start.first][start.second]=0;
deque<pair<int, int>> q;
q.push_back(start);
while(q.size()) {
pair<int, int> p = q.front();
q.pop_front();
for(int i = 0; i < 4; i++) {
int newx = p.first+dx[i], newy = p.second+dy[i];
if(newx>=0&&newy>=0&&newx<n&&newy<n&&maps[newx][newy]&&minDist[newx][newy]==1000000000) {
if((minDist[p.first][p.second]+1)/s<=temp[newx][newy]) {
minDist[newx][newy]=minDist[p.first][p.second]+1;
q.push_back({newx, newy});
}
}
}
}
return minDist[home.first][home.second]!=1000000000;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
deque<pair<int, int>> bee;
maps=vector<vector<bool>>(n, vector<bool>(n));
distBees=vector<vector<int>>(n, vector<int>(n, 1000000000));
for(int i = 0; i < n; i++) {
string t;
cin >> t;
for(int j = 0; j < n; j++) {
if(t[j]=='G') {
maps[i][j]=true;
} else if(t[j]=='M') {
start={i,j};
maps[i][j]=true;
} else if(t[j]=='D') {
home = {i,j};
} else if(t[j]=='H') {
bee.push_back({i,j});
distBees[i][j]=-1;
}
}
}
while(bee.size()) {
pair<int, int> p = bee.front();
bee.pop_front();
for(int i = 0; i < 4; i++) {
int newx = p.first+dx[i], newy = p.second+dy[i];
if(newx>=0&&newy>=0&&newx<n&&newy<n&&maps[newx][newy]&&distBees[newx][newy]==1000000000) {
distBees[newx][newy]=distBees[p.first][p.second]+1;
bee.push_back({newx, newy});
}
}
}
maps[home.first][home.second]=true;
//print(distBees);
int lo = 0, hi = distBees[start.first][start.second];
if(!possible(0)) {
cout << -1 << endl;
return 0;
}
while(lo+1<hi) {
int mid = (lo+hi)/2;
if(possible(mid)) {
lo=mid;
} else {
hi=mid;
}
}
if(possible(hi)) {
cout << hi << endl;
} else {
cout << lo << endl;
}
}
