#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
int dr[4] = {0, 0, -1, 1};
int dc[4] = {-1, 1, 0, 0};
void solve() {
int n, s; cin >> n >> s;
vector<string> grid(n);
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
auto check = [&](int cap) -> bool {
vector<vector<bool>> blocked(n, vector<bool>(n));
vector<vector<int>> dist(n, vector<int>(n, 1e9));
using state = tuple<int, int, int>;
queue<state> p, q;
state start;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'H') {
q.emplace(i, j, 0);
blocked[i][j] = true;
dist[i][j] = 0;
}
if (grid[i][j] == 'M') {
start = make_tuple(i, j, 0);
}
}
}
auto in = [&](int rr, int cc) -> bool {
return (0 <= rr and rr < n and 0 <= cc and cc < n);
};
while (!q.empty()) {
auto [r, c, d] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (in(nr, nc) and !blocked[nr][nc]) {
if (grid[nr][nc] == 'M') {
blocked[nr][nc] = true;
if (d+1 <= cap) {
return false;
}
} else if (grid[nr][nc] == 'G') {
if (d+1 > cap) {
p.emplace(nr, nc, 1);
dist[nr][nc] = 1;
} else {
q.emplace(nr, nc, d+1);
blocked[nr][nc] = true;
dist[nr][nc] = 0;
}
}
}
}
}
while (!p.empty()) {
auto [r, c, d] = p.front(); p.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (in(nr, nc) and d+1 < dist[nr][nc] and grid[nr][nc] == 'G') {
dist[nr][nc] = d+1;
p.emplace(nr, nc, d+1);
}
}
}
q.push(start);
while (!q.empty()) {
auto [r, c, d] = q.front(); q.pop();
if (d > 0 and d % s == 0) {
queue<int> oth;
}
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (in(nr, nc) and !blocked[nr][nc]) {
if (grid[nr][nc] == 'D') {
return true;
} else if (grid[nr][nc] == 'G' and (d+1) / s < dist[nr][nc]) {
q.emplace(nr, nc, d+1);
blocked[nr][nc] = true;
}
}
}
}
return false;
};
int lo = -1, hi = n * n;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (!check(mid)) {
hi = mid;
} else {
lo = mid;
}
}
if (!check(hi)) hi = lo;
cout << hi << endl;
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
}
