#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s;
vector<vector<int>> dist;
vector<vector<int>> grid;
pair<int,int> start;
pair<int,int> finish;
int debug=0;
int adebug = 0;
int INF=1000000007;
int gval(pair<int,int> cell) {
return grid[cell.first][cell.second];
}
bool bounds(pair<int,int> cell) {
return 0<=cell.first && cell.first<n && 0<=cell.second && cell.second<n;
}
vector<pair<int,int>> getnei(pair<int,int> st) {
if (!(gval(st)==0)) {
return {};
}
vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
vector<pair<int,int>> ans;
for (auto nei:V) {
if (bounds(nei) && ((gval(nei)==0) || gval(nei)==2)) {
ans.push_back(nei);
}
}
return ans;
}
bool BSTA(int time) {
//returns whether it can be done after waiting this time
vector<vector<int>> distance(n,vector<int>(n,INF));
vector<vector<int>> proc(n,vector<int>(n,0));
deque<pair<int,int>> visited={start};
distance[start.first][start.second] = 0;
if (time>=dist[start.first][start.second]) {
return 0;
}
while (visited.size()) {
pair<int,int> fi=visited[0];
visited.pop_front();
if (proc[fi.first][fi.second]) {
continue;
}
proc[fi.first][fi.second] = 1;
for (auto j:getnei(fi)) {
int bdist=time+(distance[fi.first][fi.second]+1)/s;
//it's the total number of steps the honey has to walk to reach this cell
if(debug) cout << fi.first << " " << fi.second << " " << j.first << " " << j.second << " "<<bdist << " " <<dist[fi.first][fi.second] << endl;
if (bdist>=(dist[j.first][j.second])) {
continue;
}
distance[j.first][j.second] = min(distance[j.first][j.second],distance[fi.first][fi.second]+1);
visited.push_back(j);
}
}
if(debug || adebug) cout << "BSTA TRYING METHOD CALCULATION TO FIND THE ANSWER" << " " << time << endl;
int b=distance[finish.first][finish.second] < 3*n*n;
if (debug || adebug) cout <<b << " " << distance[finish.first][finish.second] << endl;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if(debug) cout << distance[i][j] <<" ";
}
if(debug) cout << endl;
}
return distance[finish.first][finish.second] < 3*n*n;
}
vector<pair<int,int>> adjlistbee(pair<int,int> st) {
if (!(gval(st)==0 || gval(st)==3)) {
return {};
}
vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
vector<pair<int,int>> ans;
for (auto nei:V) {
if (bounds(nei) && gval(nei)==0) {
ans.push_back(nei);
}
}
return ans;
}
signed main() {
if (debug || adebug) freopen("input.txt","r",stdin);
if (debug || adebug) freopen("output.txt","w",stdout);
cin >> n >> s;
dist=vector<vector<int>>(n,vector<int>(n,INF));
grid=vector<vector<int>>(n,vector<int>(n,-1));
vector<vector<int>> proc(n,vector<int>(n,0));
vector<pair<int,int>> hives;
deque<pair<int,int>> visited;
for (int i=0; i<n; i++) {
string st;
cin >> st;
//if(debug) cout << st << endl;
for (int j=0; j<n; j++) {
//if(debug) cout << i <<" " << j << " " << st[j] << endl;
int ans;
if (st[j]=='G') {
ans=0;
}
else if (st[j]=='M') {
ans=0;
start={i,j};
}
else if (st[j]=='D') {
ans=2;
finish={i,j};
}
else if (st[j]=='T') {
ans=1;
}
else {
//assert(st[j]=='H');
ans=3;
hives.push_back({i,j});
dist[i][j] = 0;
visited.push_back({i,j});
}
grid[i][j] = ans;
//if(debug) cout << i << " " << j << endl;
}
}
//a cell is available to bees if the cell is 0 or 3, 3 denotes starting hives
//a cell is available to mecho if the dist condition holds and the cell isn't a tree
while (visited.size()) {
pair<int,int> fi=visited[0];
visited.pop_front();
if (proc[fi.first][fi.second]) {
continue;
}
proc[fi.first][fi.second] = 1;
for (auto j:adjlistbee(fi)) {
dist[j.first][j.second] = min(dist[j.first][j.second],dist[fi.first][fi.second]+1);
visited.push_back(j);
}
}
if(debug) cout << "DISTS"<< endl;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
//cout << dist[i][j] <<" ";
}
if(debug) cout << endl;
}
int l=0;
int r=n*n*1;
while (l<r) {
int m=(l+r)/2;
if (!BSTA(m)) {
l=l;
r=m;
}
else {
l=m+1;
r=r;
}
}
if (l==0 && !BSTA(l)) {
cout << -1 << endl;
return 0;
}
while (l>0 && !BSTA(l)) {
l--;
}
while (BSTA(l+1)) {
l++;
}
if (l==0 && !BSTA(l)) {
if(debug) cout << -1 << endl;
return 0;
}
cout << l << endl;
}
