#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ar array
const int mxN = 800;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int n, K;
vector<string> g(mxN);
pair<int,int> mecho, home;
vector<pair<int,int>> hives;
vector<vector<int>> disthives(mxN, vector<int>(mxN, (int) 1e11)), dist(mxN, vector<int>(mxN, (int) 1e11));
bool checkhives(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 'G' && disthives[x][y] == (int) 1e11;
}
bool checkbeer(int DIST, int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n && g[x][y] != 'T' && g[x][y] != 'H' && disthives[x][y] > DIST && dist[x][y] == (int) 1e11;
}
void bfs(int m) {
priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> pq;
pq.push({m, mecho.first, mecho.second});
while (!pq.empty()) {
int d = pq.top()[0], x = pq.top()[1], y = pq.top()[2]; pq.pop();
if (dist[x][y] < d) {
continue;
}
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
int DIST = (d + 1) / K;
// if ((d + 1) % K) {
// ++DIST;
// }
if (checkbeer(DIST, nx, ny)) {
pq.push({d + 1, nx, ny});
dist[nx][ny] = d + 1;
}
}
}
// cout << dist[home.first][home.second] << '\n';
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < n; ++j) {
// cout << dist[i][j] << ' ';
// }
// cout << '\n';
// }
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> K;
for (int i = 0; i < n; ++i) {
cin >> g[i];
for (int j = 0; j < n; ++j) {
if (g[i][j] == 'M') {
mecho = {i, j};
} else if (g[i][j] == 'D') {
home = {i, j};
} else if (g[i][j] == 'H') {
hives.push_back({i, j});
disthives[i][j] = 0;
}
}
}
priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> pq;
for (auto i : hives) {
pq.push({0, i.first, i.second});
}
while (!pq.empty()) {
int d = pq.top()[0], x = pq.top()[1], y = pq.top()[2]; pq.pop();
if (disthives[x][y] < d) {
continue;
}
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (checkhives(nx, ny)) {
pq.push({d + 1, nx, ny});
disthives[nx][ny] = d + 1;
}
}
}
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < n; ++j) {
// cout << disthives[i][j] << ' ';
// }
// cout << '\n';
// }
// cerr << "HELLO\n";
int l = 0, r = mxN * mxN;
while (l <= r) {
int m = (l + r) >> 1;
dist = vector<vector<int>>(mxN, vector<int>(mxN, (int) 1e11));
dist[mecho.first][mecho.second] = m * K;
bfs(m * K);
if (dist[home.first][home.second] < 1e11) {
l = m + 1;
} else {
r = m - 1;
}
}
cout << l - 1 << '\n';
}
