#include <bits/stdc++.h>
using namespace std;
int n, s;
int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, -1, 1};
int hiveDist[800][800];
char grid[800][800];
pair<int, int> start;
pair<int, int> dest;
vector<pair<int, int>> hives;
bool inside(int x, int y){
return x >= 0 and x < n and y >= 0 and y < n;
}
//precompute how far every cell is to the nearest hive
void bees(){
queue<pair<int, int>> trav;
fill(&hiveDist[0][0], &hiveDist[0][0]+sizeof(hiveDist)/sizeof(hiveDist[0][0]), -1);
for (pair<int, int> loc : hives){
trav.push(loc);
hiveDist[loc.first][loc.second] = 0;
}
while (!trav.empty()){
pair<int, int> curr = trav.front(); trav.pop();
for (int i = 0; i < 4; i++){
int x = curr.first+dx[i]; int y = curr.second+dy[i];
if (inside(x, y) and (grid[x][y] == 'G' or grid[x][y] == 'M') and hiveDist[x][y] == -1){
hiveDist[x][y] = hiveDist[curr.first][curr.second]+1;
trav.push({x, y});
}
}
}
}
bool bear(int wait){
queue<pair<int, int>> trav;
//time it takes for bees is floor(bearDist/s)
int bearDist[n][n];
fill(&bearDist[0][0], &bearDist[0][0]+sizeof(bearDist)/sizeof(bearDist[0][0]), -1);
trav.push(start); bearDist[start.first][start.second] = wait*s;
//check if bees can reach mecho before he even moves
int hiveToStart = hiveDist[start.first][start.second];
if (wait >= hiveToStart and hiveToStart != -1) return false;
while (!trav.empty()){
pair<int, int> curr = trav.front(); trav.pop();
//smoll bfs on reachable positions
queue<pair<int, int>> pos; pos.push(curr);
while (!pos.empty()){
pair<int, int> loc = pos.front(); pos.pop();
for (int i = 0; i < 4; i++){
int x = loc.first+dx[i]; int y = loc.second+dy[i];
if (inside(x, y) and (grid[x][y] == 'G' or grid[x][y] == 'D') and bearDist[x][y] == -1){
bearDist[x][y] = bearDist[loc.first][loc.second]+1;
//ok, mecho reached home
if (grid[x][y] == 'D') return true;
//uh oh, bees can reach here before you can
if (floor(bearDist[x][y]/s) >= hiveDist[x][y] and hiveDist[x][y] != -1) continue;
//max distance reached
int maxDist = (bearDist[curr.first][curr.second]/s)+1;
if (bearDist[x][y] == maxDist)
trav.push({x, y});
else
pos.push({x, y});
}
}
}
}
return false;
}
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> grid[i][j];
if (grid[i][j] == 'M') start = {i, j};
if (grid[i][j] == 'D') dest = {i, j};
if (grid[i][j] == 'H') hives.push_back({i, j});
}
}
bees();
//impossible
if (!bear(0)){
cout<<-1; return 0;
}
int high = n*n; int low = 0; int ans;
while (low < high){
int mid = (low+high)/2;
if (bear(mid)){
ans = mid; low = mid+1;
}
else
high = mid;
}
cout<<ans;
}
