#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define D(x) cout << #x << ':' << ' ' << x << endl;
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
enum {
T=-4,G,M,D,H=0
};
const int MX = 801;
const int sx[] = {0,1,-1,0};
const int sy[] = {1,0,0,-1};
int n,s;
pii ini, fin;
int bee[MX][MX];
//int steps[MX][MX];
int max_min = 0;
bool valid(int x){
return 0 <= x && x < n;
}
bool valid(int x, int y){
return valid(x) && valid(y);
}
void bfs(vector<pii> & hives){
queue<pii> q;
for(auto h : hives) q.push(h);
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
for(int i=0;i<4;++i){
int nx = x+sx[i];
int ny = y+sy[i];
if(valid(nx,ny) && bee[nx][ny] == G){
bee[nx][ny] = bee[x][y]+1;
max_min = max(max_min,bee[nx][ny]);
q.push({nx,ny});
}
}
}
}
/*
void step(){
queue<pii> q;
q.push(ini);
steps[ini.first][ini.second] = -1;
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
for(int i=0;i<4;++i){
int nx = x+sx[i];
int ny = y+sy[i];
if(valid(nx,ny) && steps[nx][ny] == -1 && (bee[nx][ny] > 0 || bee[nx][ny] == D)){
steps[nx][ny] = steps[x][y]+1;
q.push({nx,ny});
}
}
}
}
bool mecho(int ini_minute){
vector<vector<bool>> vis(n,vector<bool>(n,false));
queue<pii> q;
q.push(ini);
vis[ini.first][ini.second] = true;
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
for(int i=0;i<4;++i){
int nx = x+sx[i];
int ny = y+sy[i];
if(valid(nx,ny) && !vis[nx][ny]){
vis[nx][ny] = true;
if(bee[nx][ny] == D)return true;
if(bee[nx][ny] > ini_minute+((steps[nx][ny])/s))
q.push({nx,ny});
}
}
}
return false;
}
*/
bool mecho(int ini_minute){
//vector<vector<bool>> vis(n,vector<bool>(n,false));
vvi steps(n,vi(n,-1));
queue<pii> q;
q.push(ini);
//vis[ini.first][ini.second] = true;
steps[ini.first][ini.second] = 0;
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
for(int i=0;i<4;++i){
int nx = x+sx[i];
int ny = y+sy[i];
if(valid(nx,ny) && steps[nx][ny] == -1){
if(bee[nx][ny] == D)return true;
if(bee[nx][ny] > ini_minute+((steps[x][y])/s)){
//D(nx)D(ny)
steps[nx][ny] = steps[x][y]+1;
q.push({nx,ny});
}
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
vector<pii> hives;
for(int i = 0; i < n; ++i){
for(int j=0; j<n; ++j){
char c; cin >> c;
switch (c)
{
case 'T':
bee[i][j] = T;
break;
case 'M':
ini = {i,j};
bee[i][j] = M;
break;
case 'D':
fin = {i,j};
bee[i][j] = D;
break;
case 'G':
bee[i][j] = G;
break;
case 'H':
hives.emplace_back(i,j);
bee[i][j] = H;
break;
}
//steps[i][j] = -1;
}
}
bfs(hives);
//step();
/*cout << "bees\n";
for(int i = 0; i < n; ++i){
for(int j=0;j<n;++j){
cout << bee[i][j] << ' ';
}
cout << endl;
}
cout << "steps\n";
for(int i = 0; i < n; ++i){
for(int j=0;j<n;++j){
cout << steps[i][j] << ' ';
}
cout << endl;
}*/
int lo = 0,hi = max_min,ans=-1,mid;
while(lo <= hi){
mid = (lo+hi)/2;
if(mecho(mid)){
ans = mid;
lo = mid+1;
}else{
hi = mid-1;
}
}
cout << ans << endl;
return 0;
}
