#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 800 + 2;
const int inf = 1e9;
string s[N];
int b[N][N], a[N][N], n, k;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
bool Can(int x, int y) {
if (x < 0 || x >= n) return 0;
if (y < 0 || y >= n) return 0;
if (s[x][y] != 'G' && s[x][y] != 'D' && s[x][y] != 'M') return 0;
return 1;
}
int C(int x, int y) {
return (x + y - 1) / y;
}
bool Ok(int x, int y, int m) {
return (b[x][y] - C(a[x][y], k) - m) >= 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int ii, jj, iii, jjj;
ii = jj = iii = jjj = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == 'M') {
ii = i;
jj = j;
}
if (s[i][j] == 'D') {
iii = i;
jjj = j;
}
}
}
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == 'H') {
q.push({i, j});
b[i][j] = 0;
}
else b[i][j] = inf;
}
}
while (!q.empty()) {
auto u = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = u.first + dx[i];
int ny = u.second + dy[i];
if (b[nx][ny] > b[u.first][u.second] + 1 && Can(nx, ny)) {
q.push({nx, ny});
b[nx][ny] = b[u.first][u.second] + 1;
}
}
}
auto Moze = [&] (int mid) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = inf;
}
}
q.push({ii, jj});
a[ii][jj] = 0;
while (!q.empty()) {
auto u = q.front(); q.pop();
if (!Ok(u.first, u.second, mid)) continue;
for (int i = 0; i < 4; i++) {
int nx = u.first + dx[i];
int ny = u.second + dy[i];
if (a[nx][ny] > a[u.first][u.second] + 1 && Can(nx, ny)) {
q.push({nx, ny});
a[nx][ny] = a[u.first][u.second] + 1;
}
}
}
if (a[iii][jjj] == inf) return false;
return Ok(iii, jjj, mid);
};
int l = 0, r = 2 * n, ans = -1;
while (l <= r) {
int mid = l + r >> 1;
if (Moze(mid)) {
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
cout << ans << en;
return 0;
}
