#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
const int N = 805;
int n, s;
char mp[N][N];
vector<vector<int>> dis( N, vector<int> (N, -1) );
queue<pair<int,int>> q;
pair<int,int> start, home;
int dy[] = {1, 0, -1, 0}, dx[] = {0, 1, 0, -1};
bool check( int ny, int nx )
{
return (ny>=0 && ny<n && nx>=0 && nx<n && mp[ny][nx] != 'T' && mp[ny][nx] != 'D');
}
void bees()
{
while( !q.empty() )
{
auto [y, x] = q.front();
q.pop();
for( int i=0;i<4;i++ )
{
int ny=y+dy[i], nx=x+dx[i];
if( check(ny, nx) && dis[ny][nx] == -1 )
{
q.push( {ny, nx} );
dis[ny][nx] = dis[y][x]+s;
}
}
}
// for( int i=0;i<n;i++ )
// {
// for( int j=0;j<n;j++ ) cout << dis[i][j] << " ";
// cout << endl;
// }
}
bool ok( int t )
{
if( t*s >= dis[start.first][start.second] ) return false;
//cout << "out\n";
vector<vector<bool>> vis( N, vector<bool> (N, false) );
queue<tuple<int,int,int>> qq;
qq.push( {start.first, start.second, t*s} );
vis[start.first][start.second] = true;
while( !qq.empty() )
{
auto [y, x, path] = qq.front();
qq.pop();
//cout << "y " << y << " x " << x << " path " << path << endl;
for( int i=0;i<4;i++ )
{
int ny = y+dy[i], nx=x+dx[i];
if( check(ny, nx) && !vis[ny][nx] && path+1<dis[ny][nx] )
{
vis[ny][nx] = true;
qq.push( {ny, nx, path+1} );
}
}
}
for( int i=0;i<4;i++ )
{
int yy = home.first-dy[i], xx = home.second-dx[i];
if( vis[yy][xx] && check(yy, xx) ) return true;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> s;
for( int i=0;i<n;i++ )
{
for( int j=0;j<n;j++ )
{
cin >> mp[i][j];
if( mp[i][j] == 'H' )
{
q.push( {i, j} );
dis[i][j] = 0;
}
else if( mp[i][j] == 'M' ) start = {i, j};
else if( mp[i][j] == 'D' ) home ={i, j};
//cout << dis[i][j] << " ";
}
//cout << endl;
}
bees();
int l=0, r=n*n;
while( l<r )
{
int mid = (l+r)/2;
//cout << l << " " << r << " " << mid << endl;
if( ok(mid) ) l = mid+1;
else r = mid;
}
cout << l-1;
return 0;
}
