#include <iostream>
#include <queue>
using namespace std;
typedef short sh;
int const INF = 1e9+7;
int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};
int const NMAX = 800;
char mat[1 + NMAX][1 + NMAX];
int bee[1 + NMAX][1 + NMAX];
bool isValid(pair <sh, sh> to, int n) {
return (1 <= to.first && to.first <= n && 1 <= to.second && to.second <= n &&
(mat[to.first][to.second] == 'G' || mat[to.first][to.second] == 'M' || mat[to.first][to.second] == 'D'));
}
void beeBFS(int n, int step) {
queue <pair <sh, sh>> q;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
bee[i][j] = INF;
if(mat[i][j] == 'H') {
bee[i][j] = 0;
q.push({i, j});
}
}
}
while(!q.empty()) {
pair <sh, sh> from = q.front();
q.pop();
for(int dir = 0;dir < 4;dir++) {
pair <sh, sh> to = {from.first + dirX[dir], from.second + dirY[dir]};
if(isValid(to, n)) {
if(bee[from.first][from.second] + step < bee[to.first][to.second]) {
bee[to.first][to.second] = bee[from.first][from.second] + step;
q.push(to);
}
}
}
}
}
int bear[1 + NMAX][1 + NMAX];
bool bearBFS(int n, int start) {
queue <pair <sh, sh>> q;
pair <sh, sh> fin;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
bear[i][j] = INF;
if(mat[i][j] == 'M') {
bear[i][j] = start;
q.push({i, j});
}
if(mat[i][j] == 'D') {
fin = {i, j};
}
}
}
while(!q.empty()) {
pair <sh, sh> from = q.front();
q.pop();
if(bear[from.first][from.second] < bee[from.first][from.second]) {
for(int dir = 0;dir < 4;dir++) {
pair <sh, sh> to = {from.first + dirX[dir], from.second + dirY[dir]};
if(isValid(to, n) && bear[from.first][from.second] + 1 <= bear[to.first][to.second]) {
bear[to.first][to.second] = bear[from.first][from.second] + 1;
q.push(to);
}
}
}
}
if(bear[fin.first][fin.second] <= bee[fin.first][fin.second]) {
return true;
}
return false;
}
int cautbin(int from, int to, int n) {
if(from >= to) {
return from;
} else {
int mid = (from + to + 1) / 2;
if(bearBFS(n, mid)) {
return cautbin(mid, to, n);
} else {
return cautbin(from, mid-1, n);
}
}
}
void printBee(int n) {
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
cerr << bee[i][j] << ' ';
}
cerr << '\n';
}
cerr << '\n';
}
int main() {
int n, step;
cin >> n >> step;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
cin >> mat[i][j];
}
}
beeBFS(n, step);
cout << cautbin(0, n*n*step, n) / step;
return 0;
}
