#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
using namespace std;
const int mxN = 1007;
const ll inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
int n , limit;
char a[mxN][mxN];
int bee[mxN][mxN];
int dist[mxN][mxN];
pair<int , int> mecho , home;
int dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};
bool ok(int x)
{
for(int i = 0 ; i <= n ; i++)
for(int j = 0 ; j <= n ; j++) dist[i][j] = inf;
queue<pair<int , int>> q;
q.push(mecho);
dist[mecho.fi][mecho.se] = limit * x;
while(!q.empty()) {
int x = q.front().fi;
int y = q.front().se;
q.pop();
for(int d = 0 ; d < 4 ; d++) {
int newx = x + dx[d];
int newy = y + dy[d];
if(1 <= newx && newx <= n && 1 <= newy && newy <= n && a[newx][newy] == 'G') {
if(dist[newx][newy] > dist[x][y] + 1 && bee[newx][newy] > (dist[x][y] + 1) / limit) {
dist[newx][newy] = dist[x][y] + 1;
q.push({newx , newy});
}
}
}
}
if(dist[home.fi][home.se] != dist[0][0]) return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("task.inp" , "r" , stdin);
//freopen("task.out" , "w" , stdout);
cin >> n >> limit;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++) cin >> a[i][j];
memset(bee, 0x3f, sizeof bee);
queue<pair<int , int>> q;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++) {
if(a[i][j] == 'H') {
bee[i][j] = 0;
q.push({i , j});
}
if(a[i][j] == 'M') mecho = {i , j};
if(a[i][j] == 'D') home = {i , j};
}
a[home.fi][home.se] = 'G';
while(!q.empty()) {
int x = q.front().fi;
int y = q.front().se;
q.pop();
for(int d = 0 ; d < 4 ; d++) {
int newx = x + dx[d];
int newy = y + dy[d];
if(1 <= newx && newx <= n && 1 <= newy && newy <= n && a[newx][newy] == 'G') {
if(bee[newx][newy] > bee[x][y] + 1) {
bee[newx][newy] = bee[x][y] + 1;
q.push({newx , newy});
}
}
}
}
int lo = 0 , hi = inf;
while(lo + 1 < hi) {
int mid = (lo + hi) / 2;
if(ok(mid)) lo = mid;
else hi = mid;
}
if(ok(lo) == false) cout << -1;
else cout << lo;
return 0;
}
