#include <iostream>
#include <queue>
#define MAXN 805
#define INF (1LL << 40LL)
#define pii pair < lld, lld >
#define mp make_pair
using namespace std;
typedef long long lld;
lld N, S, bees[MAXN][MAXN], answer[MAXN][MAXN], Mx, My, x, y, s, e, mid, ans, ansX, ansY;
bool visited[MAXN][MAXN], val;
char forest[MAXN][MAXN];
pii aux;
queue < pii > Q;
lld dx[] = {1, -1, 0, 0};
lld dy[] = {0, 0, 1, -1};
bool valid ( lld _x, lld _y )
{
if ( _x < 0 || _x >= N )
return false;
if ( _y < 0 || _y >= N )
return false;
if ( visited[_x][_y] || forest[_x][_y] == 'T' || forest[_x][_y] == 'D')
return false;
return true;
}
bool valid2 ( lld _x, lld _y )
{
if ( _x < 0 || _x >= N )
return false;
if ( _y < 0 || _y >= N )
return false;
return true;
}
bool validM ( lld _x, lld _y )
{
if ( _x < 0 || _x >= N )
return false;
if ( _y < 0 || _y >= N )
return false;
if ( visited[_x][_y] || forest[_x][_y] == 'T')
return false;
return true;
}
bool solve ( lld v )
{
for ( lld i = 0; i < N; i++ )
for ( lld j = 0; j < N; j++ )
answer[i][j] = INF, visited[i][j] = 0;
while ( !Q.empty() )
Q.pop();
Q.push ( mp ( Mx, My ) );
answer[Mx][My] = S * v;
while ( !Q.empty() )
{
aux = Q.front();
Q.pop();
x = aux.first;
y = aux.second;
if ( x == ansX && y == ansY )
return true;
if ( answer[x][y] < bees[x][y] )
{
for ( lld i = 0; i < 4; i++ )
{
if ( validM ( x + dx[i], y + dy[i] ) )
{
Q.push ( mp ( x + dx[i], y + dy[i] ) );
answer[x + dx[i]][y + dy[i]] = answer[x][y] + 1;
visited[x + dx[i]][y + dy[i]] = 1;
}
}
}
}
return false;
}
int main ()
{
cin >> N >> S;
for ( lld i = 0; i < N; i++ )
{
for ( lld j = 0; j < N; j++ )
{
bees[i][j] = INF;
cin >> forest[i][j];
if ( forest[i][j] == 'H' )
{
Q.push ( mp ( i, j ) );
bees[i][j] = 0;
visited[i][j] = 1;
}
if ( forest[i][j] == 'M' )
Mx = i, My = j;
if ( forest[i][j] == 'D' )
ansX = i, ansY = j;
}
}
while ( !Q.empty() )
{
aux = Q.front();
Q.pop();
x = aux.first;
y = aux.second;
for ( lld i = 0; i < 4; i++ )
{
if ( valid ( x + dx[i], y + dy[i] ) )
{
Q.push ( mp ( x + dx[i], y + dy[i] ) );
bees[x + dx[i]][y + dy[i]] = bees[x][y] + S;
visited[x + dx[i]][y + dy[i]] = 1;
}
}
}
ans = -1;
s = 0, e = (1<<20);
while ( s <= e )
{
mid = (s + e) / 2;
val = solve ( mid );
if ( val )
{
ans = mid;
s = mid + 1;
}
else
e = mid - 1;
}
cout << ans << "\n";
return 0;
}
