#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(), V.end()
#define x first
#define y second
using LL = long long;
const int N = 808;
int dx[4] = {+1, -1, 0, 0};
int dy[4] = {0, 0, +1, -1};
char grid[N][N];
int n, k, bees[N][N];
pair <int, int> start, finish;
bool valid (int i, int j) {
return (i > 0 and i <= n and j > 0 and j <= n);
}
bool check (int Time) {
queue < pair <int, int> > q;
q.push (start);
vector < vector < pair <int, int> > > dist (n + 1, vector < pair <int, int> > (n + 1, {INT_MAX, 0}));
dist[start.x][start.y] = {Time, 0};
while (!q.empty ()) {
auto [X, Y] = q.front ();
q.pop ();
for (int i = 0; i < 4; i++) {
int nwX = X + dx[i], nwY = Y + dy[i];
if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'D')) {
if (dist[X][Y].x + (dist[X][Y].y == k) < dist[nwX][nwY].x and dist[X][Y].x + (dist[X][Y].y == k) <= bees[nwX][nwY]) {
if (dist[X][Y].y == k) dist[nwX][nwY] = {dist[X][Y].x + 1, 1};
else dist[nwX][nwY] = {dist[X][Y].x, dist[X][Y].y + 1};
q.push ({nwX, nwY});
}
}
}
}
return dist[finish.x][finish.y].x != INT_MAX;
}
int main() {
cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'M') start = {i, j};
if (grid[i][j] == 'D') finish = {i, j};
}
}
queue < pair <int, int> > q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (grid[i][j] == 'H') {
q.push ({i, j});
bees[i][j] = 0;
} else {
bees[i][j] = INT_MAX;
}
}
}
while (!q.empty ()) {
auto [X, Y] = q.front ();
q.pop ();
for (int i = 0; i < 4; i++) {
int nwX = X + dx[i], nwY = Y + dy[i];
if (!valid (nwX, nwY)) continue;
if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'M') and bees[X][Y] + 1 < bees[nwX][nwY]) {
bees[nwX][nwY] = bees[X][Y] + 1;
q.push ({nwX, nwY});
}
}
}
int left = 0, right = n * n;
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check (mid)) left = mid;
else right = mid - 1;
}
if (!check (left)) left--;
cout << left << '\n';
return 0;
}
