#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, x, y, u, v, k=-1; vector<vector<char>> a; vector<vector<int>> dist;
vector<vector<pair<int, int>>> dis;
int inf=1e9;
void fl1()
{
queue<array<int, 2>> q;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++){if(a[i][j]=='H'){dist[i][j]=0; q.push({i, j});}}
}
while(!q.empty())
{
auto u1=q.front(); q.pop();
if(u1[0]>0&&dist[u1[0]-1][u1[1]]>dist[u1[0]][u1[1]]+1&&(a[u1[0]-1][u1[1]]=='G'||a[u1[0]-1][u1[1]]=='M'))
{
dist[u1[0]-1][u1[1]]=dist[u1[0]][u1[1]]+1;
q.push({u1[0]-1,u1[1]});
}
if(u1[0]<n-1&&dist[u1[0]+1][u1[1]]>dist[u1[0]][u1[1]]+1&&(a[u1[0]+1][u1[1]]=='G'||a[u1[0]+1][u1[1]]=='M'))
{
dist[u1[0]+1][u1[1]]=dist[u1[0]][u1[1]]+1;
q.push({u1[0]+1,u1[1]});
}
if(u1[1]>0&&dist[u1[0]][u1[1]-1]>dist[u1[0]][u1[1]]+1&&(a[u1[0]][u1[1]-1]=='G'||a[u1[0]][u1[1]-1]=='M'))
{
dist[u1[0]][u1[1]-1]=dist[u1[0]][u1[1]]+1;
q.push({u1[0],u1[1]-1});
}
if(u1[1]<n-1&&dist[u1[0]][u1[1]+1]>dist[u1[0]][u1[1]]+1&&(a[u1[0]][u1[1]+1]=='G'||a[u1[0]][u1[1]+1]=='M'))
{
dist[u1[0]][u1[1]+1]=dist[u1[0]][u1[1]]+1; q.push({u1[0],u1[1]+1});
}
}
}
bool solve(int x1)
{
if(x1>=dist[x][y]) return false;
dis.assign(n, vector<pair<int, int>> (n));
for(int i=0; i<n; i++){for(int j=0; j<n; j++)dis[i][j]={inf, inf};}
queue<array<int, 2>> q; q.push({x, y}); dis[x][y]={x1, 0};
while(!q.empty())
{
auto u=q.front(); q.pop(); pair<int, int> ngh=dis[u[0]][u[1]]; ngh.second++;
if(ngh.second==m){ngh.first++; ngh.second=0;}
if(u[0]>0&&dist[u[0]-1][u[1]]>ngh.first&&ngh<dis[u[0]-1][u[1]]&&(a[u[0]-1][u[1]]!='T'&&a[u[0]-1][u[1]]!='H'))
{
dis[u[0]-1][u[1]]=ngh; if(a[u[0]-1][u[1]]=='D')return true;
q.push({u[0]-1,u[1]});
}
if(u[0]<n-1&&dist[u[0]+1][u[1]]>ngh.first&&ngh<dis[u[0]+1][u[1]]&&(a[u[0]+1][u[1]]!='T'&&a[u[0]+1][u[1]]!='H'))
{
dis[u[0]+1][u[1]]=ngh;if(a[u[0]+1][u[1]]=='D')return true;
q.push({u[0]+1,u[1]});
}
if(u[1]>0&&dist[u[0]][u[1]-1]>ngh.first&&ngh<dis[u[0]][u[1]-1]&&(a[u[0]][u[1]-1]!='T'&&a[u[0]][u[1]-1]!='H'))
{
dis[u[0]][u[1]-1]=ngh; if(a[u[0]][u[1]-1]=='D')return true;
q.push({u[0],u[1]-1});
}
if(u[1]<n-1&&dist[u[0]][u[1]+1]>ngh.first&&ngh<dis[u[0]][u[1]+1]&&(a[u[0]][u[1]+1]!='T'&&a[u[0]][u[1]+1]!='H'))
{
dis[u[0]][u[1]+1]=ngh; if(a[u[0]][u[1]+1]=='D')return true;
q.push({u[0],u[1]+1});
}
}
return false;
}
int main() {
cin>>n>>m; a.assign(n, vector<char> (n));dist.assign(n, vector<int> (n, inf));
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin>>a[i][j];
if(a[i][j]=='M'){x=i; y=j;}
if(a[i][j]=='D'){u=i; v=j;}
}
}
fl1();
int l=0, r=inf;
while(l<=r)
{
int m=(l+r)/2; if(solve(m)){k=m; l=m+1;} else r=m-1;
}
cout<<k<<endl;
}
