#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
int INF = 1e9;
int n, s;
vvi FloodFill (vector<pair<int, int>>& V, vvc& CharMap){
vvi ans(n, vi(n, INF));
queue<pair<int, int>> Q;
for(pair<int, int> start : V){
Q.push(start);
ans[start.first][start.second] = 0;
}
while(!Q.empty()){
pair<int, int> act = Q.front(); Q.pop();
int Xact = act.first;
int Yact = act.second;
if(Xact > 0 and ans[Xact-1][Yact] == INF and (CharMap[Xact-1][Yact] == 'G' or CharMap[Xact-1][Yact] == 'M')){
ans[Xact-1][Yact] = ans[Xact][Yact]+1;
Q.push(make_pair(Xact-1, Yact));
}
if (Yact > 0 and ans[Xact][Yact-1]== INF and (CharMap[Xact][Yact-1] == 'G' or CharMap[Xact][Yact-1] == 'M')){
ans[Xact][Yact-1] = ans[Xact][Yact]+1;
Q.push(make_pair(Xact, Yact-1));
}
if(Xact < (n-1) and ans[Xact+1][Yact] == INF and (CharMap[Xact+1][Yact] == 'G' or CharMap[Xact+1][Yact] == 'M')){
ans[Xact+1][Yact] = ans[Xact][Yact]+1;
Q.push(make_pair(Xact+1, Yact));
}
if(Yact < (n-1) and ans[Xact][Yact+1] == INF and (CharMap[Xact][Yact+1] == 'G' or CharMap[Xact][Yact+1] == 'M')){
ans[Xact][Yact+1] = ans[Xact][Yact]+1;
Q.push(make_pair(Xact, Yact+1));
}
}
return ans;
}
bool bfsMecho (pair<int, int> StartPos, int initialTime, vvi& listaAdy, vvc& CharMap){
vvi visited (n, vi(n, 0));
visited[StartPos.first][StartPos.second] = 1;
if(initialTime >= listaAdy[StartPos.first][StartPos.second]) return false;
queue<pair<int, pair<int, int>>> Q;
Q.push(make_pair(initialTime*s, StartPos));
while(!Q.empty()){
pair<int, pair<int, int>> act = Q.front(); Q.pop();
int PasosAct = act.first;
int MinuteAct = (PasosAct+1)/s;
int x = act.second.first;
int y = act.second.second;
if(CharMap[x][y] == 'D') return true;
if(x > 0 and MinuteAct < listaAdy[x-1][y] and (CharMap[x-1][y] == 'G' or CharMap[x-1][y] == 'D') and !visited[x-1][y] ){
Q.push(make_pair(PasosAct+1, make_pair(x-1, y)));
visited[x-1][y] = 1;
}
if(y > 0 and MinuteAct < listaAdy[x][y-1] and (CharMap[x][y-1] == 'G' or CharMap[x][y-1] == 'D') and !visited[x][y-1]){
Q.push(make_pair(PasosAct+1, make_pair(x, y-1)));
visited[x][y-1] = 1;
}
if(x < (n-1) and MinuteAct < listaAdy[x+1][y] and (CharMap[x+1][y] == 'G' or CharMap[x+1][y] == 'D') and !visited[x+1][y]){
Q.push(make_pair(PasosAct+1, make_pair(x+1, y)));
visited[x+1][y] = 1;
}
if(y < (n-1) and MinuteAct < listaAdy[x][y+1] and (CharMap[x][y+1] == 'G' or CharMap[x][y+1] == 'D') and !visited[x][y+1] ){
Q.push(make_pair(PasosAct+1, make_pair(x, y+1)));
visited[x][y+1] = 1;
}
}
return false;
}
int main(){
char c;
cin >> n >> s;
vector<pair<int, int>> IniciosAbejas;
pair<int, int> InicioMecho;
vvc mapa(n, vc(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
cin >> c;
//T = tree --> no one can pass
//M = mecho initially
//D = target
//G = grass
//H = hive
if(c == 'M') InicioMecho = make_pair(i, j);
else if (c == 'H') IniciosAbejas.push_back(make_pair(i, j));
mapa[i][j] = c;
}
}
vvi Matrix = FloodFill(IniciosAbejas, mapa);
int k = -1;
int hi = n*n;
int lo = 0;
while(hi >= lo){
int mid = lo + (hi-lo)/2;
if(bfsMecho(InicioMecho, mid, Matrix, mapa)){
lo = mid+1;
k = mid;
}
else hi = mid-1;
}
cout << k << endl;
/*
for(int i = 0; i < n; ++i){
cout << Matrix[i][0];
for(int j = 1; j < n; ++j){
cout << " " << Matrix[i][j];
}
cout << endl;
}*/
return 0;
}
