# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
# define pb push_back
# define pf push_front
# define For(i, a, b) for( int i = a; i < b; i++ )
# define in insert
# define all(a) a.begin(),a.end()
# define pi pair < int, int >
# define DEBUG
# define readfile(file) freopen ( (file + ".in").c_str(), "r", stdin)
# define writefile(file) freopen ( (file + ".out").c_str(), "w", stdout)
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
# define LARGE 1000
# define SET(file) readfile(file);writefile(file);
using namespace std;
int ax[4] = { 1, -1, 0, 0 };
int ay[4] = { 0, 0, 1, -1 };
char mainMap[LARGE][LARGE];
bool visited[LARGE][LARGE];
int beeDistance[LARGE][LARGE];
int n, s;
int dx, dy;
int mx, my;
bool valid( int i, int j )
{
if ( i >= 0 && i < n && j >= 0 && j < n && mainMap[i][j] != 'T' )
return 1;
return 0;
}
bool test( int delay )
{
if ( delay * s >= beeDistance[mx][my] )
return false;
memset(visited, 0, sizeof(visited));
queue < pair < int, pi > > q;
q.push({delay * s, {mx, my}});
visited[mx][my] = 1;
while (!q.empty())
{
int distance = q.front().fi;
int x = q.front().se.fi;
int y = q.front().se.se;
q.pop();
if ( mainMap[x][y] == 'D' )
return true;
For ( i, 0, 4)
{
int nx = x + ax[i];
int ny = y + ay[i];
if ( !valid(nx, ny) || visited[nx][ny] || (distance + 1) >= beeDistance[nx][ny] )
continue;
q.push({distance + 1, {nx, ny}});
visited[nx][ny] = 1;
}
}
return false;
}
int main()
{
/// Author: _Dilshod_
speed;
cin >> n >> s;
queue < pi > bq;
memset(beeDistance, -1, sizeof(beeDistance));
For ( i, 0, n )
{
For ( j, 0, n )
{
cin >> mainMap[i][j];
if ( mainMap[i][j] == 'D' )
{
dx = i;
dy = j;
} else if ( mainMap[i][j] == 'H' )
{
bq.push({i, j});
beeDistance[i][j] = 1;
} else if ( mainMap[i][j] == 'M' )
{
mx = i;
my = j;
mainMap[i][j] = 'G';
}
}
}
while( !bq.empty() )
{
int x = bq.front().fi;
int y = bq.front().se;
bq.pop();
For ( i, 0, 4 )
{
int nx = x + ax[i];
int ny = y + ay[i];
if ( !valid(nx, ny) || mainMap[nx][ny] != 'G' || beeDistance[nx][ny] != -1 )
continue;
beeDistance[nx][ny] = beeDistance[x][y] + s;
bq.push({nx, ny});
}
}
beeDistance[dx][dy] = n * n * s;
int l = -1, r = 2 * n * n, m;
while (r - l > 1 )
{
m = (l + r) >> 1;
if ( test(m) ) l = m;
else r = m;
}
cout << l;
}
