#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
using namespace std;
const int MAXN = 805, MAXM = 505, infINT = 1e9 + 234, LOG = 31, mod = 1e9 + 7;
const int dx[4] = {-1, +0, +0, +1};
const int dy[4] = {+0, +1, -1, +0};
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
struct S{
int row, col;
bool type;
S(int _row = 0, int _col = 0, bool _type = 0):
row(_row), col(_col), type(_type) {};
};
int numSize, maxRange, staX, staY, finX, finY, dist[2][MAXN][MAXN];
char board[MAXN][MAXN];
bool bee[MAXN][MAXN];
void input(){
cin >> numSize >> maxRange;
for(int row = 1; row <= numSize; row++)
for(int col = 1; col <= numSize; col++){
cin >> board[row][col];
if (board[row][col] == 'M') staX = row, staY = col;
if (board[row][col] == 'D') finX = row, finY = col;
}
}
bool isValid(int row, int col){
return 1 <= min(row, col) && max(row, col) <= numSize && board[row][col] != 'T';
}
void spread(int mid){
queue<ii> q;
memset(bee, 0, sizeof bee);
for(int row = 1; row <= numSize; row++)
for(int col = 1; col <= numSize; col++) if (board[row][col] == 'H')
q.emplace(row, col), bee[row][col] = 1;
while(mid--){
int sz = siz(q);
while(sz--){
int row = q.front().fi, col = q.front().se;
q.pop();
for(int k = 0; k < 4; k++){
int nrow = row + dx[k], ncol = col + dy[k];
if (isValid(nrow, ncol) && (board[nrow][ncol] == 'G' || board[nrow][ncol] == 'M') && !bee[nrow][ncol]){
q.emplace(nrow, ncol), bee[nrow][ncol] = 1;
}
}
}
}
}
int flr(int x){
return (x) / maxRange;
}
bool bfs(int mid){
#define PUSH(row, col, type, d) if (minimize(dist[type][row][col], d)) q.push(S(row, col, type))
queue<S> q;
memset(dist, 0x3f, sizeof dist);
for(int row = 1; row <= numSize; row++)
for(int col = 1; col <= numSize; col++) if (bee[row][col])
PUSH(row, col, 1, 0);
if (bee[staX][staY]) return 0;
PUSH(staX, staY, 0, 0);
while(q.size()){
int row = q.front().row, col = q.front().col;
bool type = q.front().type;
q.pop();
if (type == 0 && row == finX && col == finY) return 1;
for(int k = 0; k < 4; k++){
int nrow = row + dx[k], ncol = col + dy[k];
if (isValid(nrow, ncol)){
if (type == 0){
if (flr(dist[0][row][col] + 1) < dist[1][nrow][ncol]){
PUSH(nrow, ncol, type, dist[type][row][col] + 1);
}
}else{
if (board[nrow][ncol] == 'G' || board[nrow][ncol] == 'M')
PUSH(nrow, ncol, type, dist[type][row][col] + 1);
}
}
}
}
return 0;
}
bool check(const int &mid){
spread(mid);
return bfs(mid);
}
void solve(){
int l = 0, r = numSize * numSize, m, res = -1;
// cout << check(2) << '\n';
// return;
while(l <= r){
m = (l + r) >> 1;
if (check(m)) res = m, l = m + 1;
else r = m - 1;
}
cout << res << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int t = 1;
// cin >> t;
for(int T = 1; T <= t; T++) {
input();
solve();
}
cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}
