#include <iostream>
#include <vector>
using namespace std;
int n, s, dist[802][802];
pair<int, int> beg, home;
vector<pair<int, int> > hives;
void setup(){
cin >> n >> s;
for (int x = 1; x <= n; x ++){
for (int y = 1; y <= n; y ++){
dist[x][y] = -1;
char c;
cin >> c;
switch (c){
case 'T':
dist[x][y] = 0;
break;
case 'G':
break;
case 'M':
beg = make_pair(x, y);
break;
case 'D':
home = make_pair(x, y);
break;
case 'H':
dist[x][y] = 0;
hives.push_back(make_pair(x, y));
break;
}
}
}
for (int x = 0; x <= n+1; x ++){
dist[x][0] = dist[0][x] = dist[n+1][x] = dist[x][n+1] = 0;
}
}
void calc(){
vector<pair<int, int> > que = hives;
while (!que.empty()){
int i = que.front().first, j = que.front().second;
que.erase(que.begin());
if (dist[i-1][j] == -1){
dist[i-1][j] = dist[i][j] + s;
que.push_back(make_pair(i-1, j));
}
if (dist[i+1][j] == -1){
dist[i+1][j] = dist[i][j] + s;
que.push_back(make_pair(i+1, j));
}
if (dist[i][j-1] == -1){
dist[i][j-1] = dist[i][j] + s;
que.push_back(make_pair(i, j-1));
}
if (dist[i][j+1] == -1){
dist[i][j+1] = dist[i][j] + s;
que.push_back(make_pair(i, j+1));
}
}
}
bool pos(int mid){
vector<pair<pair<int, int>, int> > que;
que.push_back(make_pair(beg, mid));
while (!que.empty()){
int i = que.front().first.first, j = que.front().first.second;
int d = que.front().second;
que.erase(que.begin());
if (i == home.first && j == home.second){
return true;
}
if (dist[i-1][j] > d){
que.push_back(make_pair(make_pair(i-1, j), d+1));
}
if (dist[i+1][j] > d){
que.push_back(make_pair(make_pair(i+1, j), d+1));
}
if (dist[i][j-1] > d){
que.push_back(make_pair(make_pair(i, j-1), d+1));
}
if (dist[i][j+1] > d){
que.push_back(make_pair(make_pair(i, j+1), d+1));
}
}
return false;
}
int main() {
setup();
calc();
int lo = 0, hi = dist[beg.first][beg.second]/s+1;
while (lo <= hi){
int mid = lo + (hi-lo+1)/2;
if (pos(s*mid)){
lo = mid+1;
}else {
hi = mid-1;
}
}
cout << lo-1 << endl;
return 0;
}
