#include <bits/stdc++.h>
using namespace std;
#define int long long int
int n, s;
char grid[805][805];
int hivedist[805][805], mechodist[805][805], vis[805][805];
vector<pair<int, int>> delta = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}, hives;
pair<int, int> home, mecho;
bool valid(int i, int j) {
return (i > 0 && j > 0 && i <= n && j <= n && (grid[i][j] == 'G' || grid[i][j] == 'H' || grid[i][j] == 'M'));
}
void hivebfs() {
queue<pair<int, int>> q;
for (auto c : hives) {
q.push(c);
hivedist[c.first][c.second] = 0;
}
while(!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (auto [dx, dy] : delta) {
if (valid(a+dx, b+dy) && hivedist[a+dx][b+dy] > hivedist[a][b]+1) {
hivedist[a+dx][b+dy] = hivedist[a][b]+1;
q.push({a+dx, b+dy});
}
}
}
}
bool check(int x) {
if (hivedist[mecho.first][mecho.second] <= x) {
return 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
mechodist[i][j] = INT_MAX;
vis[i][j] = 0;
}
}
queue<pair<int, int>> q;
q.push(mecho);
mechodist[mecho.first][mecho.second] = 0;
vis[mecho.first][mecho.second] = 1;
while(!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (auto [dx, dy] : delta) {
if (valid(a+dx, b+dy) && !vis[a+dx][b+dy] && (mechodist[a][b]+1)/s+x < hivedist[a+dx][b+dy]) {
vis[a+dx][b+dy] = 1;
mechodist[a+dx][b+dy] = mechodist[a][b]+1;
q.push({a+dx, b+dy});
}
}
}
auto [a, b] = home;
for (auto [dx, dy] : delta) {
if (valid(a+dx, b+dy) && vis[a+dx][b+dy]) {
return 1;
}
}
return 0;
}
void solve() {
cin >> n >> s;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= n; j++) {
grid[i][j] = s[j-1];
mechodist[i][j] = INT_MAX;
hivedist[i][j] = INT_MAX;
if (s[j-1] == 'H') {
hives.push_back({i, j});
} else if (s[j-1] == 'M') {
mecho = {i, j};
} else if (s[j-1] == 'D') {
home = {i, j};
}
}
}
hivebfs();
int l = 0, r = 1e8;
while(l < r) {
int m = (l+r+1)/2;
if (check(m)) {
l = m;
} else {
r = m-1;
}
}
if (check(l)) {
cout << l << endl;
} else {
cout << -1 << endl;
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
t = 1;
while(t--) {
solve();
}
}
