#include <bits/stdc++.h>
#define MAX_N 801
using namespace std;
int n, s;
char grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int beed[MAX_N][MAX_N];
int steps[MAX_N][MAX_N];
bool check(int t) {
vector<pair<int, int>> hives;
pair<int, int> mecho_pos, home_pos;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
beed[i][j] = n * n;
visited[i][j] = false;
steps[i][j] = n * n;
if(grid[i][j] == 'H') {
hives.push_back({i, j});
}
if(grid[i][j] == 'M') {
mecho_pos = {i, j};
}
if(grid[i][j] == 'D') {
home_pos = {i, j};
}
}
}
queue<pair<int, int>> q;
for(auto iter : hives) {
visited[iter.first][iter.second] = true;
beed[iter.first][iter.second] = 0;
q.push(iter);
}
while(!q.empty()) {
pair<int, int> curr = q.front();
q.pop();
if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) {
visited[curr.first + 1][curr.second] = true;
beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1;
q.push({curr.first + 1, curr.second});
}
if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) {
visited[curr.first - 1][curr.second] = true;
beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1;
q.push({curr.first - 1, curr.second});
}
if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) {
visited[curr.first][curr.second + 1] = true;
beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1;
q.push({curr.first, curr.second + 1});
}
if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) {
visited[curr.first][curr.second - 1] = true;
beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1;
q.push({curr.first, curr.second - 1});
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
visited[i][j] = false;
}
}
visited[mecho_pos.first][mecho_pos.second] = true;
steps[mecho_pos.first][mecho_pos.second] = 0;
q.push(mecho_pos);
while(!q.empty()) {
pair<int, int> curr = q.front();
q.pop();
if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M' || grid[curr.first + 1][curr.second] == 'D')) {
visited[curr.first + 1][curr.second] = true;
steps[curr.first + 1][curr.second] = steps[curr.first][curr.second] + 1;
q.push({curr.first + 1, curr.second});
}
if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M' || grid[curr.first - 1][curr.second] == 'D')) {
visited[curr.first - 1][curr.second] = true;
steps[curr.first - 1][curr.second] = steps[curr.first][curr.second] + 1;
q.push({curr.first - 1, curr.second});
}
if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M' || grid[curr.first][curr.second + 1] == 'D')) {
visited[curr.first][curr.second + 1] = true;
steps[curr.first][curr.second + 1] = steps[curr.first][curr.second] + 1;
q.push({curr.first, curr.second + 1});
}
if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M' || grid[curr.first][curr.second - 1] == 'D')) {
visited[curr.first][curr.second - 1] = true;
steps[curr.first][curr.second - 1] = steps[curr.first][curr.second] + 1;
q.push({curr.first, curr.second - 1});
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
visited[i][j] = false;
}
}
if(t + 1 > beed[mecho_pos.first][mecho_pos.second]) {
return false;
}
queue<pair<pair<int, int>, int>> newq;
visited[mecho_pos.first][mecho_pos.second] = true;
newq.push({mecho_pos, 0});
while(!newq.empty()) {
pair<pair<int, int>, int> curr = newq.front();
newq.pop();
int tmp = t + 1 + ((curr.second + 1) / (s + 1));
if(curr.first.first + 1 < n && tmp <= beed[curr.first.first + 1][curr.first.second] && !visited[curr.first.first + 1][curr.first.second] && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'M' || grid[curr.first.first + 1][curr.first.second] == 'D')) {
visited[curr.first.first + 1][curr.first.second] = true;
newq.push({{curr.first.first + 1, curr.first.second}, curr.second + 1});
}
if(curr.first.first - 1 >= 0 && tmp <= beed[curr.first.first - 1][curr.first.second] && !visited[curr.first.first - 1][curr.second] && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'M' || grid[curr.first.first - 1][curr.first.second] == 'D')) {
visited[curr.first.first - 1][curr.first.second] = true;
newq.push({{curr.first.first - 1, curr.first.second}, curr.second + 1});
}
if(curr.first.second + 1 < n && tmp <= beed[curr.first.first][curr.first.second + 1] && !visited[curr.first.first][curr.first.second + 1] && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'M' || grid[curr.first.first][curr.first.second + 1] == 'D')) {
visited[curr.first.first][curr.first.second + 1] = true;
newq.push({{curr.first.first, curr.first.second + 1}, curr.second + 1});
}
if(curr.first.second - 1 >= 0 && tmp <= beed[curr.first.first][curr.first.second - 1] && !visited[curr.first.first][curr.first.second - 1] && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'M' || grid[curr.first.first][curr.first.second - 1] == 'D')) {
visited[curr.first.first][curr.first.second - 1] = true;
newq.push({{curr.first.first, curr.first.second - 1}, curr.second + 1});
}
}
return visited[home_pos.first][home_pos.second];
}
int main() {
cin >> n >> s;
for(int i = 0; i < n; i++) {
string tmp;
cin >> tmp;
for(int j = 0; j < n; j++) {
grid[i][j] = tmp[j];
}
}
int l = 0, r = 5 * n;
int ans = -1;
// true true true ... (true) false false
while(l <= r) {
int mid = l + (r - l) / 2;
if(check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans;
return 0;
}
