#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast \
ios_base::sync_with_stdio (false); \
cin.tie (NULL); \
cout.tie (NULL)
using namespace std;
vector <pair<int,int>> dir={{0,1},{0,-1},{1,0},{-1,0}};
signed main ()
{
fast;
// freopen("atlarge.in","r",stdin);
// freopen("atlarge.out","w",stdout);
int n,s;
cin>>n>>s;
string g[n];
rep(i,0,n-1)
cin>>g[i];
int lo=0;
int hi=n*n;
int best=-1;
while(lo<=hi)
{
int mid=(lo+hi)/2;
queue <pair<int,int>> q;
int disth[n][n];
rep(i,0,n-1)
rep(j,0,n-1)
disth[i][j]=mod;
rep(i,0,n-1)
rep(j,0,n-1)
if(g[i][j]=='H')
disth[i][j]=0, q.push({i,j});
while(!q.empty())
{
auto v=q.front();
q.pop();
if(disth[v.ff][v.ss]==mid)
continue;
for(auto mv:dir)
{
pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
if(g[u.ff][u.ss]=='G' || g[u.ff][u.ss]=='M')
if(disth[u.ff][u.ss]>disth[v.ff][v.ss]+1)
{
disth[u.ff][u.ss]=disth[v.ff][v.ss]+1;
q.push(u);
}
}
}
rep(i,0,n-1)
rep(j,0,n-1)
if(disth[i][j]!=mod)
{
disth[i][j]=0;
q.push({i,j});
}
while(!q.empty())
{
auto v=q.front();
q.pop();
for(auto mv:dir)
{
pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
if(g[u.ff][u.ss]=='G' || g[u.ff][u.ss]=='M')
if(disth[u.ff][u.ss]>disth[v.ff][v.ss]+1)
{
disth[u.ff][u.ss]=disth[v.ff][v.ss]+1;
q.push(u);
}
}
}
// rep(i,0,n-1)
// {
// rep(j,0,n-1)
// {
// if(disth[i][j]==mod)
// cout<<"-";
// else
// cout<<disth[i][j];
// }
// cout<<endl;
// }
// cout<<endl;
int distm[n][n];
rep(i,0,n-1)
rep(j,0,n-1)
distm[i][j]=mod;
pair <int,int> start;
rep(i,0,n-1)
rep(j,0,n-1)
if(g[i][j]=='M')
start={i,j};
distm[start.ff][start.ss]=0;
if(disth[start.ff][start.ss]!=0)
q.push(start);
while(!q.empty())
{
auto v=q.front();
q.pop();
for(auto mv:dir)
{
pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
if(g[u.ff][u.ss]=='G' || g[u.ff][u.ss]=='M' || g[u.ff][u.ss]=='D')
if(distm[u.ff][u.ss]>distm[v.ff][v.ss]+1)
{
if((distm[v.ff][v.ss]+1)/s<disth[u.ff][u.ss])
{
distm[u.ff][u.ss]=distm[v.ff][v.ss]+1;
q.push(u);
}
}
}
}
// rep(i,0,n-1)
// {
// rep(j,0,n-1)
// {
// if(distm[i][j]==mod)
// cout<<"-";
// else
// cout<<distm[i][j];
// }
// cout<<endl;
// }
// cout<<endl;
// bool cango[n][n], visited[n][n];
// rep(i,0,n-1)
// rep(j,0,n-1)
// {
// if(distm[i][j]/s<disth[i][j] && g[i][j]!='T')
// cango[i][j]=true;
// else
// cango[i][j]=false;
// visited[i][j]=false;
// }
// if(cango[start.ff][start.ss])
// q.push(start), visited[start.ff][start.ss]=true;
// rep(i,0,n-1)
// {
// rep(j,0,n-1)
// {
// if(cango[i][j])
// cout<<"+";
// else
// cout<<"-";
// }
// cout<<endl;
// }
// cout<<endl;
// while(!q.empty())
// {
// auto v=q.front();
// q.pop();
// for(auto mv:dir)
// {
// pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
// if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
// if(cango[u.ff][u.ss])
// if(!visited[u.ff][u.ss])
// {
// visited[u.ff][u.ss]=true;
// q.push(u);
// }
// }
// }
bool ok=false;
rep(i,0,n-1)
rep(j,0,n-1)
if(g[i][j]=='D')
if(distm[i][j]!=mod)
ok=true;
if(ok)
{
best=mid;
lo=mid+1;
}
else
{
hi=mid-1;
}
}
cout<<best;
return 0;
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT
*/
