#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;
ll bees_dist[MAXN][MAXN];
bool vis[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(vis, 0, sizeof(vis));
queue<pair<ll, ll>> q;
q.push(bear_coord);
vis[bear_coord.fi][bear_coord.se] = 1;
if (t >= bees_dist[bear_coord.fi][bear_coord.se]) return false;
while (!q.empty()) {
for (ll k = 0; k < s; k++) {
ll sz = q.size();
while (sz--) {
auto[x, y] = q.front();
q.pop();
if (a[x][y] == 'D') return true;
if (t >= bees_dist[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] == 'T' || a[nx][ny] == 'H') continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
t++;
}
return false;
};
auto bfs = [&](const vector<pair<ll, ll>>& srcs) {
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
bees_dist[i][j] = 1e18;
}
}
queue<pair<ll, ll>> q;
for (auto[x, y] : srcs) {
q.push({x, y});
bees_dist[x][y] = 0;
}
while (!q.empty()) {
auto[x, y] = q.front();
q.pop();
if (vis[x][y]) continue;
vis[x][y] = 1;
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] != 'G' && a[nx][ny] != 'M') continue;
if (bees_dist[nx][ny] > bees_dist[x][y] + 1) {
bees_dist[nx][ny] = bees_dist[x][y] + 1;
q.push({nx, ny});
}
}
}
};
bfs(bees_coord);
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();
}
