#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> first_biene;
pair<int,int> zuhause;
int s,n;
vector<vector<int>> dist;
bool erreichbar(int i, int j, int zeit, int gemachte_schritte){
//cout << i << " " << j << " " << gemachte_schritte << " " << zeit << endl;
/*dist[i][j] = zeit;
if(i == zuhause.first && j==zuhause.second) return true;
if (gemachte_schritte >= s){
zeit++;
gemachte_schritte = 0;
}
if (first_biene[i][j] <= zeit){
return false;
}
bool tmp = false;
if(!tmp && dist[i-1][j]>=zeit) tmp = erreichbar(i-1, j, zeit, gemachte_schritte+1);
if(!tmp && dist[i+1][j]>=zeit) tmp = erreichbar(i+1, j, zeit, gemachte_schritte+1);
if(!tmp && dist[i][j+1]>=zeit) tmp = erreichbar(i, j+1, zeit, gemachte_schritte+1);
if(!tmp && dist[i][j-1]>=zeit) tmp = erreichbar(i, j-1, zeit, gemachte_schritte+1);
return tmp;*/
vector<vector<int>> erreicht(n+2, vector<int>(n+2, 1e9));
queue<pair<int,int>> next;
next.push({i,j});
erreicht[i][j] = zeit*s;
while(!next.empty()){
int i1 = next.front().first, j1 = next.front().second;
//cout << i1 << " " << j1 << endl;
next.pop();
//cout << erreicht[i1][j1]+1 << " " << first_biene[i1][j1+1]*s << " " << erreicht[i1][j1+1] << endl;
if(i1+1==zuhause.first && j1 == zuhause.second) return true;
else if(i1==zuhause.first && j1+1 == zuhause.second) return true;
else if(i1-1==zuhause.first && j1 == zuhause.second) return true;
if(i1==zuhause.first && j1-1 == zuhause.second) return true;
if(erreicht[i1][j1]+1 < first_biene[i1][j1+1]*s && erreicht[i1][j1]+1<erreicht[i1][j1+1]){
erreicht[i1][j1+1] = erreicht[i1][j1]+1;
next.push({i1, j1+1});
}
if(erreicht[i1][j1]+1 < first_biene[i1][j1-1]*s && erreicht[i1][j1]+1<erreicht[i1][j1-1]){
erreicht[i1][j1-1] = erreicht[i1][j1]+1;
next.push({i1, j1-1});
}
if(erreicht[i1][j1]+1 < first_biene[i1+1][j1]*s && erreicht[i1][j1]+1<erreicht[i1+1][j1]){
erreicht[i1+1][j1] = erreicht[i1][j1]+1;
next.push({i1+1, j1});
}
if(erreicht[i1][j1]+1 < first_biene[i1-1][j1]*s && erreicht[i1][j1]+1<erreicht[i1-1][j1]){
erreicht[i1-1][j1] = erreicht[i1][j1]+1;
next.push({i1-1, j1});
}
}
/*for(vector<int> k: erreicht){
for(int h: k) cout << h << " ";
cout << endl;
}*/
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
pair<int,int> start;
cin >> n >> s;
vector<vector<char>> karte(n+2, vector<char>(n+2, 'T'));
first_biene = vector<vector<int>>(n+2, vector<int>(n+2,-1));
queue<pair<int,pair<int,int>>> bienen;
for (int i = 1; i <= n; i++){
for(int j=1; j<=n; j++){
cin >> karte[i][j];
if(karte[i][j]=='M'){
start = {i,j};
karte[i][j] = 'G';
}else if(karte[i][j] == 'D') zuhause = {i,j};
else if(karte[i][j] == 'T'){
first_biene[i][j] = 0;
}else if(karte[i][j] == 'H'){
first_biene[i][j] = 0;
bienen.push({0,{i,j}});
}
}
}
while(!bienen.empty()){
int zeitpunkt = bienen.front().first;
int i = bienen.front().second.first, j = bienen.front().second.second;
//cout << zeitpunkt << " " << i << " " << j << endl;
bienen.pop();
if(karte[i][j-1]=='G' && (first_biene[i][j-1]==-1 || zeitpunkt+1<first_biene[i][j-1])){
///cout << " " << i << " " << j-1 << endl;
first_biene[i][j-1] = zeitpunkt+1;
bienen.push({zeitpunkt+1, {i,j-1}});
}
if(karte[i-1][j]=='G' && (zeitpunkt+1 < first_biene[i-1][j] || first_biene[i-1][j] == -1)){
//cout << " " << i-1 << " " << j << endl;
first_biene[i-1][j] = zeitpunkt+1;
bienen.push({zeitpunkt+1, {i-1, j}});
}
if(karte[i+1][j]=='G' && (zeitpunkt+1 < first_biene[i+1][j] || first_biene[i+1][j] == -1)){
//cout << " " << i+1 << " " << j << endl;
first_biene[i+1][j] = zeitpunkt+1;
bienen.push({zeitpunkt+1, {i+1,j}});
}
if(karte[i][j+1]=='G' && (zeitpunkt+1 < first_biene[i][j+1] || first_biene[i][j+1] == -1)){
//cout << " " << i << " " << j+1 << endl;
first_biene[i][j+1] = zeitpunkt+1;
bienen.push({zeitpunkt+1, {i, j+1}});
}
}
/*for (auto y : first_biene){
for (auto x : y){
cout << x << " ";
}
cout << endl;
}
*/
int lower = 0, upper = first_biene[start.first][start.second];
while(lower<=upper){
int zeit = (upper+lower)/2;
//cout << "Zeit: " << zeit << endl;
dist = vector<vector<int>>(n+2, vector<int>(n+2, 1e9));
if(erreichbar(start.first, start.second, zeit, 0)){
//cout << "erreicht: " << zeit << endl;
lower = zeit+1;
}else{//nicht erreichbar in Zeit
//cout << "nicht: " << zeit << endl;
upper = zeit-1;
}
//cout << endl;
}
//cout << lower << " " << upper << endl;
dist = vector<vector<int>>(n+2, vector<int>(n+2, 1e9));
if(lower == 0 && !erreichbar(start.first, start.second, 0, 0)) cout << "-1" << endl;
else cout << lower-1;
return 0;
}
/*
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 0 0 0 0 -1
-1 0 5 5 5 5 5 0 -1
-1 0 4 4 4 4 4 0 -1
-1 4 3 3 3 3 3 -1 -1
-1 0 2 2 2 2 2 0 -1
-1 0 1 1 1 1 1 0 -1
-1 0 0 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
*/
