#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, S;
int startX, startY, homeX, homeY;
int bees[805][805];
char grid[805][805];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool check(int waitTime) {
if (bees[startX][startY] <= waitTime) return false;
vector<vector<int>> mechoDist(N, vector<int>(N, -1));
queue<pair<int, int>> q;
q.push({startX, startY});
mechoDist[startX][startY] = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == homeX && y == homeY) return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N &&
(grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && mechoDist[nx][ny] == -1) {
int nextDist = mechoDist[x][y] + 1;
// Mecho yetib borgan vaqtda asalarilar u yerda bo'lmasligi kerak
if (waitTime + nextDist / S < bees[nx][ny]) {
mechoDist[nx][ny] = nextDist;
q.push({nx, ny});
}
}
}
}
return false;
}
int main() {
cin >> N >> S;
queue<pair<int, int>> beeQ;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> grid[i][j];
bees[i][j] = 1e9;
if (grid[i][j] == 'H') {
beeQ.push({i, j});
bees[i][j] = 0;
} else if (grid[i][j] == 'M') {
startX = i; startY = j;
} else if (grid[i][j] == 'D') {
homeX = i; homeY = j;
}
}
}
// 1. Asalarilar BFS
while (!beeQ.empty()) {
int x = beeQ.front().first;
int y = beeQ.front().second;
beeQ.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[nx][ny] == 'G' && bees[nx][ny] == 1e9) {
bees[nx][ny] = bees[x][y] + 1;
beeQ.push({nx, ny});
}
}
}
// 2. Binar qidiruv
int low = 0, high = N * N, ans = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}
