#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
using namespace std;
#define INT long long
#define MAX_INT 2000000024
struct RICE {
int x;
int y;
int t;
};
string str;
vector<vector<int>> b, bear;
vector<string> arr;
queue<struct RICE> q;
int n, m;
void show_b() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(b[i][j] == MAX_INT) {
cout << "-1 ";
continue;
}
cout << b[i][j] << " ";
}
cout << endl;
}
}
void show_bear() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(bear[i][j] == MAX_INT) {
cout << "-1 ";
continue;
}
cout << bear[i][j] << " ";
}
cout << endl;
}
}
int in_map(int x, int y) {
if(x >= 0 && x < n && y >= 0 && y < n) return 1;
return 0;
}
void q_add(int x, int y, int t) {
if(!in_map(x, y)) return;
q.push({x, y, t});
}
void q_action(int x, int y, int t) {
if(!in_map(x, y)) return;
if(arr[x][y] != 'G' && arr[x][y] != 'H' && arr[x][y] != 'M') return;
if(b[x][y] > t) b[x][y] = t;
else return;
q_add(x+1, y, t + m);
q_add(x-1, y, t + m);
q_add(x, y+1, t + m);
q_add(x, y-1, t + m);
}
void run(int x, int y, int t) {
if(!in_map(x, y)) return;
q.push({x, y, t});
}
void run_action(int x, int y, int t) {
if(!in_map(x, y)) return;
if(arr[x][y] != 'G' && arr[x][y] != 'M' && arr[x][y] != 'D') return;
if(bear[x][y] > t) bear[x][y] = t;
else return;
if(bear[x][y] >= b[x][y]) return;
run(x+1, y, t+1);
run(x-1, y, t+1);
run(x, y+1, t+1);
run(x, y-1, t+1);
}
void clear_bear() {
int i, j;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
bear[i][j] = MAX_INT;
}
}
}
int main() {
ios::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
int i, j, k, x, y, tx, ty;
cin >> n >> m;
arr.resize(n+2);
//for(auto& num : arr) num.resize(n+2);
b.resize(n+2);
for(auto& num : b) {
num.resize(n+2);
for(auto& num2 : num) {
num2 = MAX_INT;
}
}
bear.resize(n+2);
for(auto& num : bear) {
num.resize(n+2);
}
for(i = 0; i < n; i++) {
cin >> arr[i];
for(j = 0; j < n; j++) {
if(arr[i][j] == 'H') {
q.push({i, j, 0});
}
else if(arr[i][j] == 'M') {
x = i;
y = j;
}
else if(arr[i][j] == 'D') {
tx = i;
ty = j;
}
}
}
while(!q.empty()) {
q_action(q.front().x, q.front().y, q.front().t);
q.pop();
}
//show_b();
//return 0;
int start, mid, end, ans = -1;
for(start = 0, end = n*n; start <= end; ) {
mid = (start + end)/2;
clear_bear();
q.push({x, y, mid * m});
while(!q.empty()) {
run_action(q.front().x, q.front().y, q.front().t);
q.pop();
}
//show_bear();
if(bear[tx][ty] == MAX_INT) {
end = mid-1;
}
else {
start = mid+1;
ans = max(ans, mid);
}
}
cout << ans;
return 0;
}
