#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using ll = long long;
const ll MAXN = 805;
bool beesvis[MAXN][MAXN];
bool bearvis[MAXN][MAXN];
ll dx[] = {1, -1, 0, 0};
ll dy[] = {0, 0, 1, -1};
void solve() {
ll n, s;
cin >> n >> s;
vector<string> a(n, string('?', n));
pair<ll, ll> bear_coord;
vector<pair<ll, ll>> bees_coord;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
cin >> a[i][j];
if (a[i][j] == 'M') bear_coord = {i, j};
if (a[i][j] == 'H') bees_coord.push_back({i, j});
}
}
auto good = [&](ll t) -> bool {
memset(beesvis, 0, sizeof(beesvis));
memset(bearvis, 0, sizeof(bearvis));
queue<pair<ll, ll>> beesq, bearq;
// false ako se vise nisu sirile u ovom potezu
auto bees = [&]() -> bool {
bool ret = false;
ll sz = beesq.size();
while (sz--) {
auto[x, y] = beesq.front();
beesq.pop();
for (ll i = 0; i < 4; i++) {
ll nx = x + dx[i];
ll ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (beesvis[nx][ny]) continue;
if (a[nx][ny] != 'G') continue;
beesvis[nx][ny] = 1;
ret = true;
beesq.push({nx, ny});
}
}
return ret;
};
// true ako je dosao do kuce
auto bear = [&]() -> bool {
ll sz = bearq.size();
while (sz--) {
auto[x, y] = bearq.front();
bearq.pop();
if (beesvis[x][y]) continue;
for (ll i = 0; i < 4; i++) {
ll nx = x + dx[i];
ll ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (a[nx][ny] == 'D') return true;
if (a[nx][ny] != 'G') continue;
if (beesvis[nx][ny] || bearvis[nx][ny]) continue;
bearvis[nx][ny] = 1;
bearq.push({nx, ny});
}
}
return false;
};
for (auto[x, y] : bees_coord) {
beesq.push({x, y});
beesvis[x][y] = 1;
}
bearq.push(bear_coord);
bearvis[bear_coord.fi][bear_coord.se] = 1;
while (t--) bees();
while (1) {
for (ll i = 0; i < s; i++) {
if (bear()) return true;
}
if (!bees()) return false;
}
};
ll l = -1, r = 1;
while (good(r)) r*=2;
while (r > l+1) {
ll m = (l+r)/2;
if (good(m)) l = m;
else r = m;
}
cout << l << '\n';
}
int main() {
// freopen("atlarge.in", "r", stdin);
// freopen("atlarge.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
