//memset 0x3f -> > 1000000000
#include <bits/stdc++.h>
#define f first
#define s second
#define MAXSIZE (int)(2e5+5)
// #define int long long
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef pair<int,int> ii;
string answerString[2] = {"NO", "YES"};
int add(int x, int y, int mod)
{
int t = x + y;
return t - mod * (t>=mod);
}
int sub(int x, int y, int mod)
{
int t = x - y;
return t + mod * (t<0);
}
int xd[4] = {0,0,1,-1}, yd[4] = {1,-1,0,0};
int d[808][808];
char c[808][808];
bool ch[808][808];
int mx, my, dx, dy, n, s;
vector <ii> hives;
void bfs()
{
queue <ii> q;
memset(d,0x3f,sizeof(d));
for (ii h : hives) {q.push(h); d[h.f][h.s] = 0;}
while (!q.empty())
{
ii u = q.front(); q.pop();
for (int i=0;i<4;i++)
{
ii v = {u.f + xd[i], u.s + yd[i]};
if (v.f>=1 && v.f<=n && v.s>=1 && v.s<=n
&& c[v.f][v.s] == 'G' && d[v.f][v.s]>d[u.f][u.s]+1)
{
d[v.f][v.s] = d[u.f][u.s] + 1;
q.push(v);
}
}
}
}
void dfs(int x, int y, int dt, int cnt)
{
ch[x][y] = true;
for (int i=0;i<4;i++)
{
int nx = x + xd[i], ny = y + yd[i];
if (nx>=1 && nx<=n && ny>=1 && ny<=n
&& c[nx][ny] != 'T' && dt+(cnt==0)<d[nx][ny])
{
if (cnt==0) dfs(nx,ny,dt+1,s-1);
else dfs(nx,ny,dt,cnt-1);
}
}
}
signed main()
{
//freopen("mecho.inp","r",stdin);
//freopen("text.out","w",stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>s;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
cin>>c[i][j];
if (c[i][j]=='M') {mx = i, my = j;}
if (c[i][j]=='D') {dx = i, dy = j;}
if (c[i][j]=='H') hives.push_back({i,j});
}
bfs();
/*for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) cout<<d[i][j]<<" ";
cout<<endl;
}*/
int l = -1, r = n*n+1, ans = -1;
while (l<r)
{
memset(ch,0,sizeof(ch));
//cout<<l<<" "<<r<<endl;
int m = (l + r + 1) / 2; dfs(mx, my, m, s);
if (ch[dx][dy]) l = ans = m;
else r = m - 1;
}
cout<<ans;
}
