#include <bits/stdc++.h>
using namespace std;
#define cin(vec) for(auto& i : vec) cin >> i
#define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b) for (int i = a; i < b; i++)
#define F first
#define S second
#define pb(n) push_back(n)
#define pf(n) push_front(n)
#define dci(d) fixed<<setprecision(d)
#define sp ' '
#define el '\n'
#define all(v) v.begin(),v.end()
// #define int long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=8e2+5,M=1e2+5,Mod=1e9;
char grid[N][N];
int block[N][N],n,s;
bool vis[N][N];
int valid(int i,int j){
return (i>=0&&j>=0&&i<n&&j<n);
}
struct cell{
int i;
int j;
int t;
};
queue<cell>q;
void bfs(){
while(q.size()){
int i=q.front().i;
int j=q.front().j;
int t=q.front().t;
q.pop();
if(block[i][j]<=t){
continue;
}
block[i][j]=t;
for(int k=0;k<4;k++){
int x=dx[k]+i;
int y=dy[k]+j;
if(valid(x,y)&&(grid[x][y]=='G'||grid[x][y]=='M')&&!vis[x][y]){
q.push({x,y,t+1});
}
}
}
}
bool bfs2(int i,int j,int st){
while(q.size())q.pop();
q.push({i,j,0});
vis[i][j]=1;
int t;
while(q.size()){
i=q.front().i;
j=q.front().j;
t=q.front().t;
q.pop();
if(grid[i][j]=='D')return 1;
for(int k=0;k<4;k++){
int x=dx[k]+i;
int y=dy[k]+j;
if(valid(x,y)&&(grid[x][y]=='G'||grid[x][y]=='D')&&block[x][y]>st+(t+1)/s&&!vis[x][y]){
q.push({x,y,t+1});
vis[x][y]=1;
}
}
}
return 0;
}
void testcase(int h){
cin>>n>>s;
int xst,yst,xed,yed;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
block[i][j]=1e9;
}
}
for(int i=0;i<n;i++){
string s;cin>>s;
for(int j=0;j<n;j++){
grid[i][j]=s[j];
if(s[j]=='T')
block[i][j]=-1;
if(s[j]=='H')
q.push({i,j,0});
if(s[j]=='M')xst=i,yst=j;
if(s[j]=='D')xed=i,yed=j;
}
}
bfs();
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<block[i][j]<<' ';
// }cout<<el;
// }
int l=0,r=n*n*n;
int mx=-1;
while(l<=r){
int m=(l+r)/2;
// cout<<l<<' '<<m<<' '<<r<<el;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
vis[i][j]=0;
int x=bfs2(xst,yst,m);
if(x){
mx=m;
l=m+1;
}
else{
r=m-1;
}
}
cout<<mx<<el;
}
int32_t main()
{
// fast
testcase(1);
// int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
return 0;
}
