#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, s, dist[802][802], dist2[802][802], dist3[802][802];
bool req[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] = dist2[x][y] = -1;
req[x][y] = 1;
char c;
cin >> c;
switch (c){
case 'T':
dist[x][y] = dist2[x][y] = req[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] = req[x][y] = dist2[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));
}
}
}
void mecho(){
vector<pair<int, int> > que;
que.push_back(beg);
while (!que.empty()){
int i = que.front().first, j = que.front().second;
que.erase(que.begin());
if (dist2[i-1][j] == -1){
dist2[i-1][j] = dist2[i][j]+1;
que.push_back(make_pair(i-1, j));
}
if (dist2[i][j-1] == -1){
dist2[i][j-1] = dist2[i][j]+1;
que.push_back(make_pair(i, j-1));
}
if (dist2[i+1][j] == -1){
dist2[i+1][j] = dist2[i][j]+1;
que.push_back(make_pair(i+1, j));
}
if (dist2[i][j+1] == -1){
dist2[i][j+1] = dist2[i][j]+1;
que.push_back(make_pair(i, j+1));
}
}
}
int main() {
setup();
calc();
mecho();
for (int x = 0; x <= n+1; x ++){
for (int y = 0; y <= n+1; y ++){
dist3[x][y] = (dist[x][y] - dist2[x][y] >= 0 ? (dist[x][y] - dist2[x][y]) / s : -1);
}
}
set<pair<int, pair<int, int> > > pri;
pri.insert(make_pair(dist3[beg.first][beg.second], beg));
while (!pri.empty()){
int m = pri.rbegin()->first;
int i = pri.rbegin()->second.first, j = pri.rbegin()->second.second;
pri.erase(--pri.end());
if (i == home.first && j == home.second){
cout << m << endl;
break;
}
if (req[i-1][j]){
req[i-1][j] = 0;
pri.insert(make_pair(min(m, dist3[i-1][j]), make_pair(i-1, j)));
}
if (req[i][j-1]){
req[i][j-1] = 0;
pri.insert(make_pair(min(m, dist3[i][j-1]), make_pair(i, j-1)));
}
if (req[i+1][j]){
req[i+1][j] = 0;
pri.insert(make_pair(min(m, dist3[i+1][j]), make_pair(i+1, j)));
}
if (req[i][j+1]){
req[i][j+1] = 0;
pri.insert(make_pair(min(m, dist3[i][j+1]), make_pair(i, j+1)));
}
}
return 0;
}
