#include<bits/stdc++.h>
using namespace std;
char a[1015][1015];
int bear[1105][1015];
int bee[1105][1015];
struct point{
int x, y;
};
point mep(int a, int b) {point x; x.x = a; x.y = b; return x;}
int x = -1, y = -1;
int xxx = -1, yyy = -1;
int n;
int kk;
bool can(int k) {
memset(bear, 0, sizeof bear);
bear[x][y] = k*k;
queue<point> q;
q.push(mep(x, y));
while(!q.empty()) {
int x = q.front().x, y = q.front().y;
q.pop();
if( x < n && bear[x+1][y] == 0 && (a[x+1][y] == 'G' || a[x+1][y] == 'D') && bee[x+1][y] > (bear[x][y]+1)) {bear[x+1][y] = bear[x][y] + 1;q.push(mep(x+1, y));}
if( x > 1 && bear[x-1][y] == 0 && (a[x-1][y] == 'G' || a[x-1][y] == 'D') && bee[x-1][y] > (bear[x][y]+1)) {bear[x-1][y] = bear[x][y] + 1;q.push(mep(x-1, y));}
if( y < n && bear[x][y+1] == 0 && (a[x][y+1] == 'G' || a[x][y+1] == 'D') && bee[x][y+1] > (bear[x][y]+1)) {bear[x][y+1] = bear[x][y] + 1;q.push(mep(x, y+1));}
if( y > 1 && bear[x][y-1] == 0 && (a[x][y-1] == 'G' || a[x][y-1] == 'D') && bee[x][y-1] > (bear[x][y]+1)) {bear[x][y-1] = bear[x][y] + 1;q.push(mep(x, y-1));}
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j<= n; j++) {
// cout<<bear[i][j]<<" ";
// }
// cout<<endl;
// }
return bear[xxx][yyy] != 0;
}
int main() {
cin >>n;
cin >>kk;
queue<point> p;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
bee[i][j] = INT_MAX;
cin >>a[i][j];
if(a[i][j] == 'H') {p.push(mep(i, j));bee[i][j] = 0;}
if(a[i][j] == 'M') {x = i; y = j;}
if(a[i][j] == 'D') {xxx = i; yyy = j;}
}
}
while(!p.empty()) {
int x = p.front().x, y = p.front().y;
p.pop();
if(x < n && bee[x+1][y] > bee[x][y] + 1 && (a[x+1][y] != 'T' && a[x+1][y] != 'D')) {bee[x+1][y] = bee[x][y] + kk; p.push(mep(x+1, y));}
if(x > 1 && bee[x-1][y] > bee[x][y] + 1 && (a[x-1][y] != 'T' && a[x-1][y] != 'D')) {bee[x-1][y] = bee[x][y] + kk; p.push(mep(x-1, y));}
if(y < n && bee[x][y+1] > bee[x][y] + 1 && (a[x][y+1] != 'T' && a[x][y+1] != 'D')) {bee[x][y+1] = bee[x][y] + kk; p.push(mep(x, y+1));}
if(y > 1 && bee[x][y-1] > bee[x][y] + 1 && (a[x][y-1] != 'T' && a[x][y-1] != 'D')) {bee[x][y-1] = bee[x][y] + kk; p.push(mep(x, y-1));}
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// cout<<(bee[i][j] == INT_MAX ? -1 :bee[i][j])<<" ";
// }cout<<endl;
// }
int k = 0, mm = n * n;
for(int i = mm/2; i >= 1; i /= 2)
while(i + k <= mm && can(i+k))
k += i;
cout<<(k == 0?-1:k);
}
