#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
using ii = pair<int,int>;
int N, S;
vector<int> dx = {1,0,-1,0}, dy = {0,1,0,-1};
pair<int,int> p_st, p_en;
bool in_bounds(pair<int,int> p){
return 0 <= p.f && p.f < N && 0 <= p.s && p.s < N;
}
queue<ii> push_bees(vector<vector<int>>& G, queue<ii> Q){
queue<ii> Q2;
while (!Q.empty()){
ii cur = Q.front(); Q.pop();
for (int d=0;d<4;++d){
ii nxt = {cur.f+dx[d],cur.s+dy[d]};
if (!in_bounds(nxt)) continue;
if (nxt == p_en) continue;
if (G[nxt.f][nxt.s] == 0 || (G[nxt.f][nxt.s] == 2)){
G[nxt.f][nxt.s] = -1;
Q2.push(nxt);
}
}
}
return Q2;
}
queue<ii> push_mecho(vector<vector<int>>& G, queue<ii> Q){
queue<ii> Q2;
while (!Q.empty()){
ii cur = Q.front(); Q.pop();
if (G[cur.f][cur.s] != 2) continue;
for (int d=0;d<4;++d){
ii nxt = {cur.f+dx[d],cur.s+dy[d]};
if (!in_bounds(nxt)) continue;
if (G[nxt.f][nxt.s] == 0){
G[nxt.f][nxt.s] = 2;
Q2.push(nxt);
}
}
}
return Q2;
}
bool good(int t, vector<vector<int>> G){
queue<ii> Q; // bees
for(int i=0;i<N;++i) for(int j=0;j<N;++j) if (G[i][j] == -1) Q.push({i,j});
for(int i=0;i<t;++i) Q = push_bees(G,Q);
queue<ii> Q2; Q2.push(p_st); // mecho
while(!Q2.empty()){
for (int i=0;i<S;++i) Q2 = push_mecho(G,Q2);
Q = push_bees(G,Q);
}
return G[p_en.f][p_en.s] == 2;
}
int main(){
cin >> N >> S;
vector<vector<int>> G(N,vector<int>(N,0));
for(int i=0;i<N;++i){
string st;
cin >> st;
for(int j=0;j<N;++j){
if (st[j]=='T'){
G[i][j] = 1;
}
if (st[j] == 'G'){
G[i][j] = 0;
}
if (st[j] == 'M'){
p_st = {i,j};
G[i][j] = 2;
}
if (st[j] == 'D'){
p_en = {i,j};
G[i][j] = 0;
}
if (st[j] == 'H'){
G[i][j] = -1;
}
}
}
if (!good(0,G)){
cout << -1 << endl; return 0;
}
int lo = 0, hi = 1e6;
while (lo < hi){
int mid = (lo+hi+1)/2;
if (good(mid,G)){
lo = mid;
}
else {
hi = mid-1;
}
}
cout << lo << endl;
}
