#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Cell {
int x, y, time;
};
int N, S;
vector<string> forest;
vector<vector<int>> beeTime;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void bfsBees(queue<Cell>& q) {
while (!q.empty()) {
Cell cell = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = cell.x + dx[d], ny = cell.y + dy[d];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && forest[nx][ny] == 'G' && beeTime[nx][ny] == -1) {
beeTime[nx][ny] = cell.time + 1;
q.push({nx, ny, cell.time + 1});
}
}
}
}
bool canMechoSurvive(int waitTime, pair<int, int> start, pair<int, int> home) {
queue<Cell> q;
vector<vector<int>> mechoTime(N, vector<int>(N, -1));
q.push({start.first, start.second, 0});
mechoTime[start.first][start.second] = 0;
while (!q.empty()) {
Cell cell = q.front(); q.pop();
if (cell.x == home.first && cell.y == home.second) return true;
for (int d = 0; d < 4; d++) {
int nx = cell.x + dx[d], ny = cell.y + dy[d];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && forest[nx][ny] != 'T' && forest[nx][ny] != 'H' && mechoTime[nx][ny] == -1) {
int reachTime = cell.time + 1;
int mechoArrival = reachTime * S + waitTime;
if (mechoArrival < beeTime[nx][ny]) {
mechoTime[nx][ny] = reachTime;
q.push({nx, ny, reachTime});
}
}
}
}
return false;
}
int main() {
cin >> N >> S;
forest.resize(N);
beeTime.assign(N, vector<int>(N, -1));
queue<Cell> bees;
pair<int, int> mecho, home;
for (int i = 0; i < N; i++) {
cin >> forest[i];
for (int j = 0; j < N; j++) {
if (forest[i][j] == 'M') mecho = {i, j};
else if (forest[i][j] == 'D') home = {i, j};
else if (forest[i][j] == 'H') {
bees.push({i, j, 0});
beeTime[i][j] = 0;
}
}
}
bfsBees(bees);
int left = 0, right = N * N, answer = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canMechoSurvive(mid, mecho, home)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << answer << endl;
return 0;
}
