#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,a,b,c) for(ll i = a;i<b;i+=c)
#define fre(i,a,b,c) for(int i = a;i>=b;i-=c)
#define fs first
#define sc second
#define all(a) a.begin(),a.end()
#define IINF 2000000005
#define LINF 1000000000000000005
#define str string
#define endl '\n'
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using tiiii = tuple<int,int,int,int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
constexpr int MOD = 1000000007;
//998244353
str a[805];
int n,k;
int pf[805][805];
bool vis[805][805];
int sx,sy,ex,ey;
bool ch(int m){
fr(i,0,n,1)fill(vis[i],vis[i] + n,0);
queue<tiiii> q;
q.push({m + 1,k,sx,sy});
vis[sx][sy] = 1;
while(!q.empty()){
auto [t,d,x,y] = q.front();
q.pop();
if(d == 0){
if(pf[x][y] == t){
vis[x][y] = 0;
continue;
}
t++;
d = k;
}
// cout << x << ' ' << y << ' ' << t << ' ' << d << endl;
fr(i,0,4,1){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < n && a[nx][ny] != 'T' && !vis[nx][ny] && pf[nx][ny] >= t){
vis[nx][ny] = 1;
q.push({t,d - 1,nx,ny});
}
}
}
// fr(i,0,n,1){
// fr(j,0,n,1)cout << vis[i][j] << ' ';cout << endl;
// }
return vis[ex][ey];
}
int main(){
cin >> n >> k;
fr(i,0,n,1)cin >> a[i];
fr(i,0,n,1)fill(pf[i],pf[i] + n,IINF);
queue<tiii> q;
fr(i,0,n,1){
fr(j,0,n,1){
if(a[i][j] == 'H'){
pf[i][j] = 0;
q.push({0,i,j});
}
if(a[i][j] == 'M'){
sx = i;
sy = j;
}
if(a[i][j] == 'D'){
ex = i;
ey = j;
}
}
}
while(!q.empty()){
auto [d,x,y] = q.front();
pf[x][y] = d;
q.pop();
fr(i,0,4,1){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < n && a[nx][ny] == 'G' && !vis[nx][ny]){
vis[nx][ny] = 1;
q.push({d + 1,nx,ny});
}
}
}
int l = 0,r = 1e9,ans = -1;
while(l <= r){
int m = (l + r)/2;
if(ch(m)){
l = m + 1;
ans = m;
}else{
r = m - 1;
}
}
cout << ans;
// fr(i,0,n,1){
// fr(j,0,n,1)cout << (pf[i][j] == IINF ? -1 : pf[i][j]) << ' ';cout << endl;
// }
// ch(3);
}
