#include <bits/stdc++.h>
using namespace std;
struct Node
{
bool g=true;
int beesat=INT_MAX;
};
int N,S;
complex<int> start;
complex<int> end;
vector<vector<Node>> cell;
bool outOfRange(complex<int> a)
{
return a.real() < 0 || a.real() >= N || a.imag() < 0 || a.imag() >= N;
}
template<typename T>
T& at(vector<vector<T>>& v,complex<int> p)
{
return v[p.real()][p.imag()];
}
bool bfs(int m)
{
queue<pair<complex<int>,int>> q;
vector<vector<char>> seen(N,vector<char>(N,false));
q.push({start,S*m});
while(q.size())
{
auto a = q.front(); q.pop();
if(at(seen,a.first)) continue;
at(seen,a.first)=true;
if(at(cell,a.first).beesat <= a.second) continue;
if(a.first==::end) return true;
for(auto i : initializer_list<complex<int>>{{1,0},{-1,0},{0,1},{0,-1}})
{
if(outOfRange(a.first+i)) continue;
if(a.first+i!=::end&&!at(cell,a.first+i).g) continue;
q.push({a.first+i,a.second+1});
}
}
return false;
}
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
cin >> N >> S;
cell.assign(N,vector<Node>(N));
queue<complex<int>> bees;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
char a;
cin >> a;
switch(a)
{
case 'D':
::end = {i,j};
case 'T':
cell[i][j].g = false;
break;
case 'M':
start = {i,j};
break;
case 'H':
cell[i][j].beesat = 0;
bees.push({i,j});
case 'G':
;
}
}
}
while(bees.size())
{
auto a = bees.front();bees.pop();
for(complex<int> i : initializer_list<complex<int>>{{1,0},{-1,0},{0,1},{0,-1}})
{
auto b = a+i;
if(outOfRange(b)) continue;
if (!at(cell,b).g || at(cell,b).beesat < INT_MAX) continue;
at(cell,b).beesat = at(cell,a).beesat+S;
bees.push(b);
}
}
int l = -1;
int r = N*N;
while(l < r-1)
{
int m = (l+r)/2;
if (bfs(m))
l = m;
else
r = m;
}
cout << l << "\n";
}
