#include <bits/stdc++.h>
#define inf 100000000000000007
#define mod 1000000007
#define rnd() dist(rand_num)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
using namespace std;
unsigned seed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
uniform_int_distribution<int> dist(0,inf);
template <typename T> void read(T &x){
x=0;char ch=getchar();int fh=1;
while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
x*=fh;
}
template <typename T> void write(T x) {
if (x<0) x=-x,putchar('-');
if (x>9) write(x/10);
putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int n,s;
char mp[805][1005];
int bee[805][805];
int bear[805][805];
bool check(int mid)
{
memset(bear,0x3f,sizeof(bear));
queue<pair<int,int>> q;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(mp[i][j]=='M')
{
if(mid*s>=bee[i][j]) return false;
bear[i][j]=mid*s;
q.push(make_pair(i,j));
}
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop();
if(mp[p.first][p.second]=='D') return true;
for(int d=0;d<4;++d)
{
int xx=p.first+dx[d],yy=p.second+dy[d];
if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mp[xx][yy]!='T'&&mp[xx][yy]!='H'&&bear[p.first][p.second]+1<bee[xx][yy]&&bear[xx][yy]>bear[p.first][p.second]+1)
{
bear[xx][yy]=bear[p.first][p.second]+1;
q.push(make_pair(xx,yy));
}
}
}
return false;
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
read(n);read(s);
for(int i=1;i<=n;++i)
scanf("%s",mp[i]+1);
memset(bee,0x3f,sizeof(bee));
queue<pair<int,int>> q;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(mp[i][j]=='H')
{
bee[i][j]=0;
q.push(make_pair(i,j));
}
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop();
for(int d=0;d<4;++d)
{
int xx=p.first+dx[d],yy=p.second+dy[d];
if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&(mp[xx][yy]=='G'||mp[xx][yy]=='M')&&bee[xx][yy]>bee[p.first][p.second]+s)
{
bee[xx][yy]=bee[p.first][p.second]+s;
q.push(make_pair(xx,yy));
}
}
}
int l=0,r=5000000;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
if(check(l)) writeln(l);
else puts("-1");
return 0;
}
